Cod sursa(job #594842)

Utilizator balakraz94abcd efgh balakraz94 Data 9 iunie 2011 20:07:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define infile "ctc.in"
#define outfile "ctc.out"
#define n_max 100005 
using namespace std;

void citeste();
void rezolva();
void afiseaza();

vector < vector <int> > v(n_max,1), vt(n_max,1);

vector <int> rez(1),uz(n_max),post(1);

int n,m,nr;


void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d", &n,&m);
	
	int x,y;
	
	for(;m;m--)
	{
		scanf("%d %d",&x,&y);
		
		v[x].push_back(y);
		vt[y].push_back(x);
		
		v[x][0]++;
		vt[y][0]++;
	}
	
	fclose(stdin);
}



void dfs(int nod)
{
	uz[nod]=1;
	
	for(int i=1; i<=v[nod][0];i++)
		if(!uz[v[nod][i]])
			dfs(v[nod][i]);

	post.push_back(nod);
}


void dfst(int nod)
{
	uz[nod]=0;
	
	rez.push_back(nod);
	
	for(int i=1;i<=vt[nod][0];i++)
		if(uz[vt[nod][i]])
			dfst(vt[nod][i]);
}


void rezolva()
{
	for(int i=1;i<=n;i++)
		if(!uz[i])
			dfs(i);
		
	for(int i=n;i;i--)
		if(uz[post[i]])
		{
			nr++;
			dfst(post[i]);
			rez.push_back(0);
		}
}




void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%d\n",nr);
	
	for(int i=1;nr;i++)
		if(!rez[i])
		{
			printf("\n");
			nr--;
		}
		else
			printf("%d ",rez[i]);

	fclose(stdout);
}


int main()
{
	citeste();
	rezolva();
	afiseaza();
	
	return 0;
}