Cod sursa(job #238922)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 3 ianuarie 2009 17:40:05
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX=100001;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> G[NMAX];
stack<int> S;
int N,M,s[NMAX],nr[NMAX],low[NMAX];
bool u[NMAX];
vector< vector<int> > C;
int nc,index;
vector<int> aux;
void DF(int vf){
     int k;
     vector<int>::iterator it;
     S.push(vf);
     u[vf]=true;
     nr[vf]=++index;
     low[vf]=nr[vf];
     
     for (it=G[vf].begin();it!=G[vf].end();++it)
       if (!nr[*it]) 
         DF(*it),low[vf]=min(low[vf],low[*it]);
       else 
         if (u[*it]) low[vf]=min(low[vf],low[*it]);

     if (low[vf]==nr[vf]){
       ++nc;
       aux.clear();
       do { 
         k=S.top();
         S.pop();
         u[k]=false;
         aux.push_back(k);
          }
       while (k!=vf);
       C.push_back(aux);
       }  
     }
int main(){
    int i,j;
    vector<int>::iterator it;
    
    fin>>N>>M;
    while (M--){
      fin>>i>>j;
      G[i].push_back(j);
      }
    
    for (i=1;i<=N;++i)
     if (!nr[i]) DF(i);
       
    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;
}