#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n , m;
int F[N][N] , X[N] , par[N];
vector<pair<int , int>> edges;
vector<int> adj[N];
queue<int> Q;
int ok;
int D[N];
void q(int u, int v){
memset(X , 0 , sizeof(X));
memset(par ,0 , sizeof(par));
for(int i = 1; i <= n; ++i){
if(F[i][u] && F[i][v]) X[i] = 1;
}
for(int i = 1; i<= n; ++i) D[i] = 2e9;
D[u] =0;
Q.push(u);
while(Q.size()){
int x = Q.front();
Q.pop();
for(int y : adj[x]){
if(X[y] || (x == u && y == v))continue;
if(D[y] > D[x] + 1){
D[y] = D[x] + 1;
par[y] = x;
Q.push(y);
}
}
}
if(D[v] == 2e9) return;
int U= v;
while(1){
cout << U << " ";
if(U == u)break;
U = par[U];
}
ok = 1;
}
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
int u ,v;
for(int i= 0; i< m; ++i){
cin >> u >> v;
F[u][v] = 1; F[v][u] = 1;
adj[u].emplace_back(v); adj[v].emplace_back(u);
edges.emplace_back(u , v);
}
mt19937 rng(time(0));
shuffle(edges.begin() , edges.end() , rng);
//for(auto x : edges)cout << x.first << " " << x.second<<endl;
for(int i = 0; i < min(5700 , (int)edges.size()); ++i){
q(edges[i].first , edges[i].second);
if(ok)break;
}
if(!ok)cout << "no";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
716 KB |
Output is correct |
2 |
Correct |
9 ms |
716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
1624 KB |
Output is correct |
2 |
Correct |
2 ms |
1612 KB |
Output is correct |
3 |
Correct |
5 ms |
1612 KB |
Output is correct |
4 |
Correct |
75 ms |
1652 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
1612 KB |
Output is correct |
2 |
Correct |
83 ms |
1592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
5208 KB |
Output is correct |
2 |
Correct |
8 ms |
4812 KB |
Output is correct |
3 |
Correct |
584 ms |
5192 KB |
Output is correct |
4 |
Correct |
338 ms |
4816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
173 ms |
4684 KB |
Output is correct |
2 |
Correct |
992 ms |
4684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
3908 KB |
Output is correct |
2 |
Correct |
34 ms |
3908 KB |
Output is correct |
3 |
Correct |
33 ms |
5548 KB |
Output is correct |
4 |
Correct |
618 ms |
5444 KB |
Output is correct |