Cod sursa(job #236041)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 26 decembrie 2008 17:14:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
/*
  Componente tare conexe
  Alg. Kosaraju-Sharir
*/
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
const int NMAX=100001;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> G[NMAX],GT[NMAX];
int N,M,s[NMAX],nr;
bitset<NMAX> viz;
vector< vector<int> > C;
int nc;
void DF(int vf){
     vector<int>::iterator it;
     viz[vf]=1;
     for (it=G[vf].begin();it!=G[vf].end();++it)
      if (!viz[*it]) DF(*it);
     s[++nr]=vf;
     }
vector<int> aux;
void DFT(int vf){
     vector<int>::iterator it;
     viz[vf]=0;
     aux.push_back(vf);
     for (it=GT[vf].begin();it!=GT[vf].end();++it)
      if (viz[*it]) DFT(*it);
     }
int main(){
    int i,j;
    vector<int>::iterator it;
    
    fin>>N>>M;
    while (M--){
      fin>>i>>j;
      G[i].push_back(j);
      GT[j].push_back(i);
      }
    
    for (i=1;i<=N;++i)
     if (!viz[i]) DF(i);
    
    for (i=N;i;i--)
     if (viz[s[i]]){
       ++nc;
       aux.clear();
       DFT(s[i]);
       C.push_back(aux);}
       
    fout<<nc<<'\n';
    for (i=0;i<nc;++i){
      for (it=C[i].begin();it!=C[i].end();++it)
        fout<<*it<<' ';
      fout<<'\n';}
      
    return 0;
}