Cod sursa(job #871705)

Utilizator enedumitruene dumitru enedumitru Data 5 februarie 2013 03:17:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio> 
#include <vector> 
#define Nmax 100002
using namespace std; 
vector <int> g[Nmax], gt[Nmax],cm[Nmax]; 
int n,m,c,ctc,i,x,y,postviz[Nmax],viz[Nmax]; 
void df(int nod) 
{   viz[nod]=1; 
	vector <int> :: iterator it=g[nod].begin(), sf=g[nod].end();
    for(;it!=sf;++it) 
		if (!viz[*it]) df(*it); 
    postviz[++c]=nod; 
} 
void dft(int nod) 
{   viz[nod]=0; 
    cm[ctc].push_back(nod); 
	vector <int> :: iterator it=gt[nod].begin(), sf=gt[nod].end();
    for(;it!=sf;++it) 
        if (viz[*it]) dft(*it); 
} 
int main() 
{   freopen("ctc.in","r",stdin); 
    freopen("ctc.out","w",stdout); 
    scanf("%d%d",&n,&m); 
    for(i=1;i<=m;i++) 
        {   scanf("%d%d",&x,&y); 
            g[x].push_back(y); gt[y].push_back(x); 
        } 
    for(i=1;i<=n;i++) 
        if(!viz[i]) df(i); 
    for(i=n;i>=1;i--) 
		if(viz[postviz[i]]) {ctc++; dft(postviz[i]);} 
     printf("%d\n",ctc); 
     for (i=1;i<=ctc;i++) 
		 {	for (unsigned int j=0;j<cm[i].size();j++) printf("%d ",cm[i][j]); 
			printf("\n"); 
		 } 
    return 0; 
}