#include <bits/stdc++.h>
#define maxn 1005
#define inf 10000009
// #define fin std::cin
// #define fout std::cout
std::ifstream fin("potemkin.in");
std::ofstream fout("potemkin.out");
int V, E;
bool adj[maxn][maxn];
bool visited[maxn];
bool ok[maxn];
int dist[maxn], parent[maxn];
std::vector <int> edge[maxn];
void dfs(int node, std::vector <int>& comp) {
visited[node] = true;
comp.push_back(node);
for(auto next: edge[node]) {
if(visited[next] == true or ok[next] == false)
continue;
dfs(next, comp);
}
}
void solve(std::vector <int> nodes) {
if(nodes.size() == 0)
return;
int root = nodes[0];
std::vector <int> neighbours, other;
for(int i = 1; i < nodes.size(); i ++){
visited[nodes[i]] = false;
if(adj[root][nodes[i]] == true)
neighbours.push_back(nodes[i]);
else
other.push_back(nodes[i]);
}
for(int i = 1; i <= V; i ++)
ok[i] = false;
for(auto i: other)
ok[i] = true;
std::vector <std::vector <int>> comps;
for(auto i: other) {
if(visited[i] == true)
continue;
std::vector <int> aux;
dfs(i, aux);
comps.push_back(aux);
}
int node1 = -1, node2 = -1;
for(auto comp: comps) {
std::vector <int> crtNext;
for(int next: neighbours) {
for(int node: comp) {
if(adj[node][next] == true) {
for(int t: crtNext) {
if(adj[next][t] == false) {
node1 = next;
node2 = t;
break;
}
}
if(node1 == -1)
crtNext.push_back(next);
break;
}
}
if(node1 != -1)
break;
}
if(node1 == -1)
continue;
for(int i = 1; i <= V; i ++)
dist[i] = -1;
for(int i: comp)
dist[i] = inf;
dist[node2] = inf;
dist[node1] = 1;
std::queue <int> q;
q.push(node1);
while(q.empty() == false) {
int node = q.front();
q.pop();
for(int next: edge[node]) {
if(dist[next] == inf) {
dist[next] = dist[node] + 1;
parent[next] = node;
q.push(next);
}
}
}
std::vector <int> sol;
sol.push_back(node2);
while(node2 != node1) {
node2 = parent[node2];
sol.push_back(node2);
}
fout << root << ' ';
for(auto i: sol)
fout << i << ' ';
fout << '\n';
exit(0);
}
solve(neighbours);
for(auto comp: comps) {
std::vector <int> aux = comp;
for(int next: neighbours) {
for(int node: comp) {
if(adj[node][next] == true) {
aux.push_back(next);
break;
}
}
}
solve(aux);
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
fin >> V >> E;
for(int i = 0, src, dest; i < E; i ++) {
fin >> src >> dest;
adj[src][dest] = adj[dest][src] = true;
edge[src].push_back(dest);
edge[dest].push_back(src);
}
std::vector <int> nodes;
for(int i = 1; i <= V; i ++)
nodes.push_back(i);
solve(nodes);
fout << "no\n";
return 0;
}
Compilation message
indcyc.cpp: In function 'void solve(std::vector<int>)':
indcyc.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i = 1; i < nodes.size(); i ++){
| ~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Too short sequence |
2 |
Incorrect |
0 ms |
332 KB |
Unexpected end of file - token expected |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Too short sequence |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Too short sequence |
2 |
Incorrect |
1 ms |
332 KB |
Unexpected end of file - token expected |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Too short sequence |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Too short sequence |
2 |
Incorrect |
0 ms |
332 KB |
Unexpected end of file - token expected |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
332 KB |
Unexpected end of file - token expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Too short sequence |
2 |
Incorrect |
0 ms |
332 KB |
Unexpected end of file - token expected |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Too short sequence |
2 |
Correct |
0 ms |
332 KB |
Too short sequence |
3 |
Incorrect |
0 ms |
332 KB |
Unexpected end of file - token expected |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Too short sequence |
2 |
Incorrect |
0 ms |
332 KB |
Unexpected end of file - token expected |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Too short sequence |
2 |
Incorrect |
0 ms |
332 KB |
Unexpected end of file - token expected |
3 |
Halted |
0 ms |
0 KB |
- |