Cod sursa(job #693798)

Utilizator balakraz94abcd efgh balakraz94 Data 27 februarie 2012 16:52:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<vector>
#define infile "ctc.in"
#define outfile "ctc.out"
#define n_max 100005 
#define pb push_back
#define nxt *it
#define FOR(g) \
    for(vector<int> :: iterator it = g.begin(); it!=g.end(); ++it)
using namespace std;


vector < int > v[n_max], vt[n_max];

vector < int > post, sol[n_max];

bitset < n_max > viz;

int N, M, Nsol;


void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d", &N, &M);
	
	int x,y;
	
	while(M--)
	{
		scanf("%d %d",&x,&y);
		
		v[x].pb(y);
		vt[y].pb(x);
	}
	
	fclose(stdin);
}


void DFS(int x)
{	
	viz[x] = 1;
	
	FOR(v[x])
		if(!viz[nxt])
			DFS(nxt);
		
	post.pb(x);
}



void DFST(int x)
{
	viz[x] = 0;
	
	FOR(vt[x])
		if(viz[nxt])
			DFST(nxt);
		
	sol[Nsol].pb(x);
}



void rezolva()
{
	for(int i=1; i<=N; ++i)
		if(!viz[i])
			DFS(i);
		
	reverse(post.begin(), post.end());
	
	FOR(post)
	    if(viz[nxt]){
			Nsol++;
			
			DFST(nxt);
		}
}




void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%d\n",Nsol);
	
	for(int i=1; i<=Nsol; ++i){
		FOR(sol[i])
			printf("%d ",nxt);
		
		printf("\n");
	}

	fclose(stdout);
}


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