Cod sursa(job #423738)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 24 martie 2010 11:02:25
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define FIN "ctc.in"
#define FOUT "ctc.out"
#define NMAX 100005
#define MMAX 200004
using namespace std;

vector <int> Gn[NMAX],Gt[NMAX],REZ[NMAX],adj;
int COLOR[NMAX],n,m,x,y,nr;

void DFS(vector<int> *graf , int nod , int Col ,  vector<int> &rez )
{vector<int>::iterator it;
 COLOR[nod]=Col;
 for ( it=graf[nod].begin() ; it!=graf[nod].end() ; it++  )
     if(COLOR[*it]==Col-1)
      DFS(graf,*it,Col,rez);
 rez.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++)
     {scanf("%d %d",&x,&y);
      Gn[x].push_back(y);
      Gt[y].push_back(x);
     }
    for(int i=1;i<=n;i++)
     if(COLOR [ i ]== 0 ) 
       {nr++;
         adj.clear();
        DFS(Gn,i,1,adj);
        DFS(Gt,i,2,REZ[nr]);
       vector<int>::iterator it; 
       for(it=adj.begin();it!=adj.end();it++)
        if(COLOR[*it]==1) COLOR[*it]=0;
       }
    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;
    }