Cod sursa(job #384767)

Utilizator swift90Ionut Bogdanescu swift90 Data 20 ianuarie 2010 21:27:56
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
#include<vector>
using namespace std;
vector <int> nr[100100],nrt[100100],sol[100100];
vector <bool> viz(100100,false);
int n,m,t[100100],cc[100100],c;
void df(int x){
	if(viz[x])
		return;
	viz[x]=true;
	for(vector<int>::iterator i=nr[x].begin();i!=nr[x].end();++i)
		df(*i);
	t[++t[0]]=x;
}
void dft(int x){
	if(viz[x])
		return;
	viz[x]=true;
	cc[x]=c;
	for(vector<int>::iterator i=nrt[x].begin();i!=nrt[x].end();++i)
		dft(*i);
}
void afis(){
	printf("%d\n",c);
	for(int i=1;i<=n;++i)
		sol[cc[i]].push_back(i);
	for(int i=1;i<=c;++i){
		for(vector<int>::iterator it=sol[i].begin();it!=sol[i].end();++it)
			printf("%d ",*it);
		printf("\n");
	}
}
int main(){
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	int i,x,y;
	scanf("%d%d",&n,&m);
	for(;m;--m){
		scanf("%d%d",&x,&y);
		nr[x].push_back(y);
		nrt[y].push_back(x);
	}
	for(i=1;i<=n;++i)
		df(i);
	for(i=0;i<=n;++i)
		viz[i]=false;
	for(i=t[0];i;--i){
		if(!cc[t[i]]){
			++c;
			dft(t[i]);
		}
	}
	afis();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}