Cod sursa(job #963951)

Utilizator alinaelenaFMI Colceag Alina alinaelena Data 19 iunie 2013 19:37:26
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<stdlib.h>

using namespace std;

int n,m;
vector <int> graf[100001],suc,pred,graf2[100001],ctc[1000];
int viz[100001];


 void read()
 {
	 int x,y,i;
	 scanf("%d %d",&n,&m);
	 for (i=1;i<=m;++i)
		{ scanf("%d %d",&x,&y); graf[x].push_back(y);}
	 
 }

 
 void transpunere()
 {
	 int x,y,i,j;
	
	 for (i=1;i<=n;++i)
		 for (j=0;j<graf[i].size();++j)
		{ graf2[graf[i][j]].push_back(i);}
	 
 }

 int num;
 
 void dfs1(int nod)
 {
	 int i;
	 viz[nod]=1;
	
	 int l=graf[nod].size();
	 for (i=0;i<l;++i)
		 if (!viz[graf[nod][i]]) dfs1(graf[nod][i]);
	  suc.push_back(nod);
 }
 
  void dfs2(int nod)
 {
	 int i;
	 viz[nod]=1;
	
	 int l=graf2[nod].size();
	 for (i=0;i<l;++i)
		 if (!viz[graf2[nod][i]]) dfs2(graf2[nod][i]);
	  ctc[num].push_back(nod);
 }
 
 
/*void solve()
{
	int i,j;
	int l=suc.size();
	for (i=l-1;i>=0;--i)
		
}*/

 void write()
{
	printf("%d\n",num);
	for  ( int i=1;i<=num;++i)
		{for (int j=0;j<=ctc[i].size()-1;++j)
			printf("%d ",ctc[i][j]); printf("\n"); }
		
 }

void setviz()
{
	memset(viz,0,sizeof(viz));
}
  
int main ()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	
	read();
	int i;
	for (i=1;i<=n;++i)
		if (!viz[i])
				dfs1(i);
	transpunere();
	setviz();
		int l=suc.size();
	for (i=l-1;i>=0;--i)
		if (!viz[suc[i]])
				{num++;dfs2(suc[i]);}
	//solve();
	write();
}