#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 1000;
const int MAX_M = 100000;
int N, M;
vector<int> gp[MAX_N+1];
vector<pii> edge;
bool chk[MAX_N+1];
bool chk2[MAX_N+1];
bool chkg[MAX_N+1];
int g[MAX_N+1];
int find_g(int x){
if(x==g[x]) return x;
return g[x] = find_g(g[x]);
}
void union_g(int x, int y){
x = find_g(x), y = find_g(y);
g[x] = y;
}
int from[MAX_N+1];
deque<int> dq;
void answer(int x, int y, int z){
from[y] = x; from[z] = y;
dq.pb(z);
while(!dq.empty()){
int now = dq.front();
dq.pop_front();
if(now==x) break;
for(auto i : gp[now]){
if(i==x || !chk[i]){
if(from[i]==0){
from[i] = now; dq.push_back(i);
}
}
}
}
while(1){
printf("%d ", x); if(x==y) break;
x = from[x];
}
}
int check[MAX_N+1][MAX_N+1];
vector<int> gnum;
int ivgn[MAX_N+1];
int main(){
scanf("%d%d", &N, &M);
rep(i, M){
int a, b; scanf("%d%d", &a, &b);
gp[a].pb(b); gp[b].pb(a);
edge.pb({a, b});
}
rep(i, N){
rep(j, N) g[j] = j;
chk[i] = true;
for(auto j: gp[i]) chk[j] = true;
for(auto p : edge){
if(chk[p.first] || chk[p.second]) continue;
union_g(p.first, p.second);
}
gnum.clear();
for(int j=1; j<=N; j++){
if(find_g(j) == j){
gnum.push_back(j);
ivgn[j] = gnum.size()-1;
}
}
for(auto p : edge){
if(chk[p.first] && !chk[p.second]){
check[p.first][ivgn[find_g(p.second)]] = true;
}else if(!chk[p.first] && chk[p.second]){
check[p.second][ivgn[find_g(p.first)]] = true;
}
}
for(int j=0; j<gp[i].size(); j++){
int now = gp[i][j];
for(auto k : gp[now]){
if(chk[k]) chk2[k] = true;
else chkg[find_g(k)] = true;
}
for(int j2=j+1; j2<gp[i].size(); j2++){
int now2 = gp[i][j2];
if(now2==now || chk2[now2]) continue;
for(int k = 0; k<gnum.size(); k++){
if(check[now][k] && check[now2][k]){
answer(now, i, now2);
return 0;
}
}
}
for(auto k : gp[now]){
if(chk[k]) chk2[k] = false;
else chkg[find_g(k)] = false;
}
}
for(auto p : edge){
if(chk[p.first] && !chk[p.second]){
check[p.first][ivgn[find_g(p.second)]] = false;
}else if(!chk[p.first] && chk[p.second]){
check[p.second][ivgn[find_g(p.first)]] = false;
}
}
for(auto j : gp[i]) chk[j] = false;
chk[i] = false;
}
printf("no"); return 0;
}
Compilation message
indcyc.cpp: In function 'int main()':
indcyc.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<gp[i].size(); j++){
~^~~~~~~~~~~~~
indcyc.cpp:108:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j2=j+1; j2<gp[i].size(); j2++){
~~^~~~~~~~~~~~~
indcyc.cpp:111:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = 0; k<gnum.size(); k++){
~^~~~~~~~~~~~
indcyc.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
indcyc.cpp:76:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a, b; scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
512 KB |
Output is correct |
| 2 |
Correct |
8 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1624 KB |
Output is correct |
| 2 |
Correct |
4 ms |
640 KB |
Output is correct |
| 3 |
Correct |
5 ms |
768 KB |
Output is correct |
| 4 |
Correct |
56 ms |
1528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
768 KB |
Output is correct |
| 2 |
Correct |
44 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
3184 KB |
Output is correct |
| 2 |
Correct |
12 ms |
2172 KB |
Output is correct |
| 3 |
Correct |
694 ms |
5188 KB |
Output is correct |
| 4 |
Correct |
251 ms |
4852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1536 KB |
Output is correct |
| 2 |
Execution timed out |
1084 ms |
3420 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
3812 KB |
Output is correct |
| 2 |
Correct |
323 ms |
2160 KB |
Output is correct |
| 3 |
Correct |
121 ms |
2800 KB |
Output is correct |
| 4 |
Execution timed out |
1045 ms |
4076 KB |
Time limit exceeded |
