Cod sursa(job #775461)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 8 august 2012 11:19:53
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream>
#include<vector>
#define lim 100006
using namespace std;


ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int>G[lim],T[lim],Solutie[lim];
int n,m,i,j,x,y,ctc,dim;
int viz[lim],Mark[lim],st[lim];
void DFP(int nod ) {
	viz[nod]=1;
	
	for(int i=0;i<G[nod].size();++i)
		if(!viz[G[nod][i]])
			DFP(G[nod][i]);
	st[++dim]=nod;
}
void DFM(int nod,int ctc){
	
	Mark[nod]=ctc;
	
	
	for(int i=0;i<T[nod].size();++i)
		if(!Mark[T[nod][i]])
			DFM(T[nod][i],ctc);
	
}
int main (){
	
	f>>n>>m;
	
	for(i=1;i<=m;i++){
		f>>x>>y;
		G[x].push_back(y);
		T[y].push_back(x);
	}
	
	for(i=1;i<=n;++i)
		if(!viz[i])
			DFP(i);
	for(;dim;st[dim--]=0){
		
		if(Mark[st[dim]]==0)
			DFM(st[dim],++ctc);
		
	}
	for(i=1;i<=n;++i)
		Solutie[Mark[i]].push_back(i);
	g<<ctc<<"\n";
	for(int i=1;i<=ctc;i++){
		
		for(int j=0;j<Solutie[i].size();++j)
			
			g<<Solutie[i][j]<<" ";
		g<<"\n";
	}
	return 0;
}