Cod sursa(job #1217568)

Utilizator pavlov.ionPavlov Ion pavlov.ion Data 7 august 2014 19:15:10
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
#define MAXN 100005
#define pb push_back
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int N,M,viz[MAXN];
vector<int> G[MAXN],GT[MAXN];
stack<int> st;
void DFS(int x) {
	int i;	
	for(i=0;i<G[x].size();i++)
	             if (!viz[G[x][i]]) { viz[G[x][i]]=1;
	                                  DFS(G[x][i]); }
	st.push(x);
}
void DFST(int x){
int i;
viz[x]=1;
for(i=0;i<GT[x].size();i++)
           if(!viz[GT[x][i]]) 
		                  DFST(GT[x][i]);
cout<<x<<" "; 
}
int main() {
	int i,x,y;
	cin>>N>>M;
	for(i=1;i<=M;i++) {
		       cin>>x>>y;
			   G[x].pb(y);
			   GT[y].pb(x);  }
	memset(viz,0,sizeof(viz));		   
	for(i=1;i<=N;i++) 
		   if (!viz[i]) { viz[i]=1;
		   	  			  DFS(i);  }			  		   			  
	memset(viz,0,sizeof(viz));
	while(st.size()>0) {
		     x=st.top();
			 st.pop();
			 if(!viz[x]) {
			        DFST(x);
					cout<<"\n";  }	  
}				            
  return 0;
}