#include <bits/stdc++.h> using namespace std; vector<int>G[50],G_reverse[50]; int finishing_time,finish[50],visited[50]; int DFS(int n) { finishing_time++; int i,j,k; visited[n]=1; for(i=0,j=G[n].size(); i<j; i++) { k=G[n][i]; if(visited[k]==0) DFS(k); } finish[n]=++finishing_time; return 0; } int dfs2(int n) { printf(" %d",n); visited[n]=1; int i,j,k; for(i=0,j=G_reverse[n].size(); i<j; i++) { k=G_reverse[n][i]; if(visited[k]==0) dfs2(k); } return 0; } int main() { int i,j,k,m,n,e; printf("Enter no of nodes in the graph:"); cin>>n; printf("Enter no of edges in the graph:"); cin>>e; while(e--) { cin>>i>>j; G[i].push_back(j); G_reverse[j].push_back(i); } memset(visited,0,sizeof visited); finishing_time=0; for(i=1; i<=n; i++) { if(visited[i]==0) { DFS(i); } } vector<pair<int,int> >v; for(i=1; i<=n; i++) { v.push_back(make_pair(finish[i],i)); } sort(v.begin(),v.end()); reverse(v.begin(),v.end());//sorting in ascending order. int SCC=0; memset(visited,0,sizeof visited); for(i=0; i<n; i++) { m=v[i].second; if(!visited[m]) { printf("Component of SCC no %d:",++SCC); dfs2(m); printf("\n"); } } return 0; }
Subscribe
Login
0 Comments