Cod sursa(job #424306)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 24 martie 2010 19:10:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define FIN "ctc.in"
#define FOUT "ctc.out"
#define NMAX 100005

using namespace std;

vector<int> Gi[NMAX],Gt[NMAX],rez[NMAX],aux;
int n,m,COLOR[NMAX];

void DFS(vector<int> G[NMAX],int nod,int C,vector<int> & aux )
{COLOR[nod]=C;
 vector<int>::iterator i;
 for(i=G[nod].begin();i!=G[nod].end();i++)
  if(COLOR[*i]==C-1) 
   DFS(G,*i,C,aux);
 aux.push_back(nod);      
 }

int main()
{
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
     {int x,y;
      scanf("%d %d",&x,&y);
      Gi[x].push_back(y);
      Gt[y].push_back(x);       
     }
     for(int i=1;i<=n;i++)
      if(COLOR[i]==0) DFS(Gi,i,1,aux);
    vector<int>::iterator i;
    int nr=0;
    for(;aux.size();aux.pop_back())
     if(COLOR[aux.back()]!=2)
      {nr++;
      DFS(Gt,aux.back(),2,rez[nr]);
      }
     printf("%d\n",nr); 
     for(int i=1;i<=nr;i++)
      {vector<int>::iterator it;
       for(it=rez[i].begin();it!=rez[i].end();it++)
        printf("%d ",*it);
        printf("\n");     
             } 
    return 0;
    }