Cod sursa(job #871704)

Utilizator enedumitruene dumitru enedumitru Data 5 februarie 2013 03:09:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio> 
#include <vector> 
#define Nmax 100002
using namespace std; 
vector <int> g[Nmax], gt[Nmax],cm[Nmax]; 
int n,m,c,ctc,postviz[Nmax],viz[Nmax]; 
void df(int nod) 
{   unsigned int i; 
    viz[nod]=1; 
    for(i=0;i<g[nod].size();i++) 
		if (!viz[g[nod][i]]) df(g[nod][i]); 
    postviz[++c]=nod; 
} 
void dft(int nod) 
{   unsigned int i; 
    viz[nod]=0; 
    cm[ctc].push_back(nod); 
    for (i=0;i<gt[nod].size();i++) 
        if (viz[gt[nod][i]]) dft(gt[nod][i]); 
} 
int main() 
{   freopen("ctc.in","r",stdin); 
    freopen("ctc.out","w",stdout); 
    int i,x,y;
    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; 
}