Untitled
plain_text
a month ago
1.3 kB
2
Indexable
Never
#include<unordered_map> #include<vector> #include<list> #include<stack> //directed unweighted graph //1st step void dfs(int node, vector<bool>&vis, stack<int>&s, unordered_map<int,list<int>> &adjlist){ vis[node]=true; for(auto nbr:adjlist[node]){ if(!vis[nbr]){ dfs(nbr,vis,s,adjlist); } } s.push(node); } void revdfs(int node,vector<bool>&vis, unordered_map<int,list<int>> &transpose){ vis[node]=true; for(auto nbr:transpose[node]){ if(!vis[nbr]){ revdfs(nbr,vis,transpose); } } } int stronglyConnectedComponents(int v, vector<vector<int>> &edges) { unordered_map<int,list<int>> adjlist; for(int i=0;i<edges.size();i++){ int u=edges[i][0]; int v=edges[i][1]; adjlist[u].push_back(v); } stack<int> s; vector<bool> vis(v,false); for(int i=0;i<v;i++){ if(!vis[i]) dfs(i,vis,s,adjlist); } //transpose graph 2nd step unordered_map<int,list<int>> transpose; for(int i=0;i<v;i++){ vis[i]=0; for(auto nbr:adjlist[i]){ transpose[nbr].push_back(i); } } //traverse with stack int count=0; while(!s.empty()){ int top=s.top(); s.pop(); if(!vis[top]) { count++; //here the count is inceremted not inside revdfs revdfs(top,vis,transpose); } } return count; } //