Cod sursa(job #508475)

Utilizator paul992Cirstean Paul paul992 Data 8 decembrie 2010 16:21:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<stdio.h>
#include<algo.h>
#include<vector>
#define pb push_back
using namespace std;
vector<int> a[100001];
vector<int> at[100001];

int n,m,viz[100001],c[100001],nr,k;


void dfs(int x)
{vector<int>::iterator it;
viz[x]=1;
for(it=a[x].begin();it!=a[x].end();it++)
	if(!viz[*it])dfs(*it);
c[++k]=x;}

void dfs1(int x,int ok)
{vector<int>::iterator it;
if(ok)printf("%d ",x);
viz[x]=1;
for(it=at[x].begin();it!=at[x].end();it++)
	if(!viz[*it])dfs1(*it,ok);
}




int main()
{freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int x,y;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{scanf("%d %d",&x,&y);
a[x].pb(y);
at[y].pb(x);}

for(int i=1;i<=n;i++)
	if(viz[i]==0)
		dfs(i);

fill(&viz[0],&viz[n+1],0);

for(int i=n;i>=1;i--)
	if(viz[c[i]]==0)
	{nr++;
	dfs1(c[i],0);}

fill(&viz[0],&viz[n+1],0);

printf("%d\n",nr);

for(int i=n;i>=1;i--)
	if(viz[c[i]]==0)
	{
		dfs1(c[i],1);
	printf("\n");
	}
	


return 0;}