Submission #110589

#TimeUsernameProblemLanguageResultExecution timeMemory
110589someone_aaPotemkin cycle (CEOI15_indcyc)C++17
100 / 100
307 ms2704 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair using namespace std; const int maxn = 1100; vector<int>g[maxn]; bool edge[maxn][maxn]; bool blocked_node[maxn]; bool visited[maxn]; int parent[maxn]; int n, m; class dsu { public: int uparent[maxn], usize[maxn]; int n; void init(int _n) { n = _n; for(int i=1;i<=n;i++) { uparent[i] = i; usize[i] = 1; } } int uroot(int x) { while(x != uparent[x]) { x = uparent[x]; } return x; } void unite(int x, int y) { x = uroot(x); y = uroot(y); if(usize[x] > usize[y]) { uparent[y] = x; usize[x] += usize[y]; } else { uparent[x] = y; usize[y] += usize[x]; } } bool connected(int x, int y) { return uroot(x) == uroot(y); } }D; void dfs(int node) { visited[node] = true; if(blocked_node[node]) return; for(int i:g[node]) { if(!visited[i]) { //cout<<node<<" Calling "<<i<<"\n"; dfs(i); D.unite(i, node); } } } bool find_path(int s, int i, int j) { memset(visited,false,sizeof(visited)); visited[s] = true; visited[i] = true; parent[s] = 0; parent[i] = s; queue<int>q; q.push(i); while(!q.empty()) { int curr = q.front(); q.pop(); for(int i:g[curr]) { if(!visited[i] && (!blocked_node[i] || i == j)) { visited[i] = true; parent[i] = curr; q.push(i); } } } if(!visited[j]) return false; int x = j; while(x) { cout<<x<<" "; x = parent[x]; } return true; } int main() { cin>>n>>m; int u, v; for(int i=0;i<m;i++) { cin>>u>>v; edge[u][v] = edge[v][u] = true; g[u].pb(v); g[v].pb(u); } bool found = false; for(int s=1;s<=n;s++) { // consider s as the start of the cycle // remove all edges from s, and break the graph in subgraphs memset(visited,false,sizeof(visited)); memset(blocked_node,false,sizeof(blocked_node)); visited[s] = true; for(auto i:g[s]) { blocked_node[i] = true; } D.init(n); for(int i=1;i<=n;i++) { if(!visited[i]) { dfs(i); } } for(int i:g[s]) { for(int j:g[s]) { if(i < j && !edge[i][j] && D.connected(i, j)) { //cout<<s<<" call: "<<i<<" to "<<j<<"\n"; found = find_path(s, i, j); } if(found) break; } if(found) break; } if(found) break; } if(!found) { cout<<"no\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...