### psionic_08's blog

By psionic_08, history, 4 months ago,

Can anyone help me out with this problem, I looked up on many places but couldn't find any satisfactory solution

• -10

 » 4 months ago, # |   0 you can just simply search for cycle in undirected graph and keep a parent array if you find cycle just backtrack using parent array
•  » » 4 months ago, # ^ |   0 tried that but it fails in the case my dfs starting point is in the cycle as it would have no parent
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Once you reach an already visited node X which isn't the parent keep pushing parent-nodes into vector until you reach X Then terminate the dfs and print the ans
 » 4 months ago, # | ← Rev. 4 →   0 To solve the problem, you just need to look for any cycle in the graph. To do this, you can perform a dfs and keep track of the tree it generates using an array of parents, where $parent[v] = u$ if $v$ is a direct descendant of $u$, and for the root node, you can set $parent[root] = -1$.Suppose we are at node $u$, and let $v$ be a direct child of $u$. Then there exists a cycle if $v$ has a $backedge$ with an ancestor node of $u$ in the DFS tree, or if $v$ has a descendant node that has a $backedge$ with an ancestor node of $u$.Let $v$ be the node with a $backedge$ to $w$ ancestor of $u$. Therefore, we can traverse in reverse order from $v$ to $w$ using the parent array and construct an array $ans$ composed by $[w, ..., u, v,w]$, which would be our cycle.Time Complexity: $O(n + m)$ My solution#include using namespace std; const int oo = 1e9; const int maxn = 1e5 + 5; vector g[maxn]; int pi[maxn]; bool visited[maxn]; vector ans; bool dfs(int u, int p) { visited[u] = true; pi[u] = p; for(auto v: g[u]) { if( v == p ) continue; if( visited[v] ) { // backedge while(u != v) { ans.push_back(u); u = pi[u]; } ans.push_back(v); ans.push_back(ans[0]); return true; } if( dfs(v, u) ) return true; } return false; } int main() { // freopen("in.txt", "r", stdin); int n, m; cin >> n >> m; for(int i = 0; i < m; i ++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } bool hascycle = false; fill(pi, pi + maxn, -1); for(int u = 1; u <= n; u ++) { if( visited[u] ) continue; if( (hascycle = dfs(u, -1)) == true ) break; } if( !hascycle ) { cout << "IMPOSSIBLE\n"; } else { cout << ans.size() << endl; for(auto u: ans) cout << u << ' '; cout << endl; } } 
•  » » 4 months ago, # ^ |   0 thanks man