Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- char color[100];
- stack<int> dfs_visit(list<int>*adj,stack<int>sagor,int source)
- {
- color[source]='g';
- list<int>::iterator it;
- for(it=adj[source].begin();it!=adj[source].end();++it)
- {
- if(color[*it]=='w')
- {
- sagor=dfs_visit(adj,sagor,*it);
- }
- }
- color[source]='b';
- sagor.push(source);
- return sagor;
- }
- stack<int> topo(list<int>*adj,int node)
- {
- stack<int>sagor;
- stack<int>jerin;
- for(int i=1;i<=node;i++)
- {
- color[i]='w';
- }
- for(int i=1;i<=node;i++)
- {
- if(color[i]=='w')
- {
- sagor=dfs_visit(adj,sagor,i);
- }
- }
- return sagor;
- }
- list<int> dfs_visit1(list<int>*radj,list<int>sagor,int source)
- {
- color[source]='g';
- list<int>::iterator it;
- for(it=radj[source].begin();it!=radj[source].end();++it)
- {
- if(color[*it]=='w')
- {
- sagor=dfs_visit1(radj,sagor,*it);
- }
- }
- color[source]='b';
- sagor.push_back(source);
- return sagor;
- }
- list<int> scc(list<int>*radj,int node,int source)
- {
- list<int>sagor;
- sagor=dfs_visit1(radj,sagor,source);
- return sagor;
- }
- int main()
- {
- ///strongly connected components
- cout<<"input case numbers : ";
- int case1;
- cin>>case1;
- for(int temp=1;temp<=case1;temp++)
- {
- int node,edge;
- cout<<"input node numbers : ";
- cin>>node;
- cout<<"input edge numbers : ";
- cin>>edge;
- list<int>adj[node+1];
- list<int>radj[node+1];
- for(int tp=1;tp<=edge;tp++)
- {
- int x,y;
- cin>>x>>y;
- adj[x].push_back(y);
- radj[y].push_back(x);
- }
- stack<int>data;
- data=topo(adj,node);
- int mark=0;
- list<int>components[node+1];
- for(int i=1;i<=node;i++)
- {
- color[i]='w';
- }
- while(!data.empty())
- {
- if(color[data.top()]=='w')
- {
- components[++mark]=scc(radj,node,data.top());
- }
- data.pop();
- }
- for(int i=1;i<=mark;i++)
- {
- list<int>::iterator it;
- cout<<i<<" conponent's node : ";
- for(it=components[i].begin();it!=components[i].end();++it)
- {
- cout<<*it<<" ";
- }
- cout<<"\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement