Cod sursa(job #631810)

Utilizator CBogdanCiobanu Bogdan CBogdan Data 9 noiembrie 2011 19:55:13
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<cstdio>
#include<vector>
using namespace std;

int n,m,x,y,T,i,COMP,viz[100010],f[100010];
vector<int> G[100010],GT[100010],comp[100010];
vector<int> Q;

void read(),solve(),dfs(int),dfs1(int);

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		GT[y].push_back(x);
	}
}

void solve()
{
	vector<int>::reverse_iterator rit;
	for(i=1;i<=n;i++)
	{
		if(viz[i]!=1)
			dfs(1);
	}
/*	for(iit=Q.begin();iit!=Q.end();iit++)
		printf(" %d ",*iit);
	printf("\n");
	for(i=1;i<=n;i++)printf(" %d ",f[i]);*/
	
	for(rit=Q.rbegin();rit!=Q.rend();rit++)
	{
		if(viz[*rit]!=2)
		{
			COMP++;
			dfs1(*rit);
		}
	}
	vector<int>::iterator it;
	printf("%d\n",COMP);
	for(i=1;i<=COMP;i++)
	{
		for(it=comp[i].begin();it!=comp[i].end();it++)printf("%d ",*it);
		printf("\n");
	}
	
}

void dfs(int nod)
{
	vector<int>::iterator it;
	viz[nod]=1;
	for(it=G[nod].begin();it!=G[nod].end();it++)
	{
		if(viz[*it]!=1)
			dfs(*it);
	}
	++T;
	Q.push_back(nod);
	f[nod]=T;
}

void dfs1(int nod)
{
	vector<int>::iterator it;
	viz[nod]=2;
	for(it=GT[nod].begin();it!=GT[nod].end();it++)
	{
		if(viz[*it]!=2)
			dfs1(*it);
	}
	comp[COMP].push_back(nod);
	
}