Cod sursa(job #633741)

Utilizator blue_phoenixPosea Elena blue_phoenix Data 14 noiembrie 2011 18:18:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define maxn 100005

vector <int> graf[maxn],graft[maxn],tc[maxn];//tc[i] tine toate nodurile din componenta conexa a i-a
int stiva[maxn],vf=0,conex;

bool viz[maxn];

void dfs1(int start){//parcurg graful direct si bag in stiva
    int i;
    viz[start]=1;
    for(i=0;i<graf[start].size();i++){
         if(!viz[graf[start][i]]){
            dfs1(graf[start][i]);
         }
    }
    stiva[vf]=start;
    vf++;
}

void dfs2(int start){//parcurg graful transpus
    int i;
    viz[start]=0;
    tc[conex].push_back(start);
    for(i=0;i<graft[start].size();i++){
         if(viz[graft[start][i]]){
            dfs2(graft[start][i]);
         }
    }
}


int  main(){
  int n,m;
  FILE *fin=fopen("ctc.in","r");
  FILE *fout=fopen("ctc.out","w");
  int i,j;
  int a,b;
  fscanf(fin,"%d%d",&n,&m);
  for(i=0;i<m;i++){
        fscanf(fin,"%d%d",&a,&b);
        graf[a].push_back(b);
        graft[b].push_back(a);
  }
  //nodurile incep de la 1
  for(i=1;i<=n;i++)
    if(!viz[i]){
       dfs1(i);
    }

  conex=0;
  for(i=n-1;i>=0;i--){
     if(viz[stiva[i]]){
         dfs2(stiva[i]);
         conex++;
     }
  }
  //afisez
  fprintf(fout,"%d\n",conex);
  for(i=0;i<conex;i++){//a i-a componenta conexa
    for(j=0;j<tc[i].size();j++)
     fprintf(fout,"%d ",tc[i][j]);
    fprintf(fout,"\n");
  }
return 0;
}