Untitled
unknown
plain_text
3 years ago
1.5 kB
6
Indexable
//{ Driver Code Starts #include <bits/stdc++.h> using namespace std; // } Driver Code Ends class Solution { public: // Function to detect cycle in an undirected graph. bool dfs(int node,vector<int>& vis,vector<vector<int>>& adj,int last) { for(auto it:adj[node]) { if(it==last) continue; if(vis[it]) return true; vis[it] = true; if(dfs(it,vis,adj,node)) return true; } return false; } bool isCycle(int V, vector<int> adj[]) { vector<int> vis(V,0); vector<vector<int>> aadj(V); for(int i=0;i<V;i++) { for(auto it:adj[i]) aadj[i].push_back(it); } for(int i=0;i<V;i++) { if(vis[i]) continue; vis[i] = true; if(dfs(i,vis,aadj,-1)) return true; } return false; } }; //{ Driver Code Starts. int main() { int tc; cin >> tc; while (tc--) { int V, E; cin >> V >> E; vector<int> adj[V]; for (int i = 0; i < E; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } Solution obj; bool ans = obj.isCycle(V, adj); if (ans) cout << "1\n"; else cout << "0\n"; } return 0; } // } Driver Code Ends
Editor is loading...