Cod sursa(job #657968)

Utilizator informatician28Andrei Dinu informatician28 Data 7 ianuarie 2012 18:14:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<fstream>
#include<vector> 

using namespace std; 

ifstream in("ctc.in"); 
ofstream out("ctc.out"); 

#define pb push_back 
#define NMAX 100001

vector< int > G[NMAX], Gt[NMAX], sol[NMAX]; 

int N, M, timp=0, viz[NMAX], ordine[NMAX], nr=0 ; 

void DFS(int nod) 
{
	
	for(vector< int > :: iterator it = G[nod].begin(); it != G[nod].end(); ++it) 
		if(!viz[*it]) 
			{
				viz[*it] = 1; 
				DFS(*it); 
						}
		ordine[++timp] = nod; 
}

void DFSt(int nod) 
{
	viz[nod] = 0; 
	sol[nr].pb(nod); 
	
	for(vector< int > :: iterator it = Gt[nod].begin(); it != Gt[nod].end(); ++it) 
		if(viz[*it]) 
            DFSt(*it); 
}		
			
	
int main() 
{
	int i, j, x, y;
	in >> N >> M; 
	
	for(i = 1; i <= M; i++) 
	{
		in >> x >> y; 
		G[x].pb(y); 
		Gt[y].pb(x); 
	}

	
	for(i = 1; i <= N; i++) 
		if(!viz[i]) 
			{
				viz[i] = 1; 
				DFS(i);
		}
		
		for(i = N; i > 0; --i) 
			if(viz[ordine[i]]) 
				{
					++nr; 
					DFSt(ordine[i]);
			}
			
		out << nr << '\n'; 
	
			for(i = 1; i <= nr; ++i) 
			{
				for(j = 0; j < sol[i].size(); ++j)
					out << sol[i][j] << " "; 
				
				out << '\n'; 
			}
			
			return 0; 
}