Cod sursa(job #656580)

Utilizator giuliastefGiulia Stef giuliastef Data 4 ianuarie 2012 20:39:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
// componente tare conexe

#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <iterator>
#define NMAX 100011
using namespace std;
vector <int> G[NMAX],con;
stack <int> S;
vector <vector<int> > C;
int n,m,niv;
int idx[NMAX],lowlink[NMAX];
bool in_s[NMAX];
inline int minim(int a, int b){
      if(a<=b) return a;
      return b;
}
void read(){
     int i,x,y;
     ifstream f("ctc.in");
     f>>n>>m;
     for(i=1;i<=m;++i){
      f>>x>>y;
      G[x].push_back(y);
      idx[i]=-1;
     }
}
void dfs(int nod){
     idx[nod]=lowlink[nod]=niv;
     niv++;
     S.push(nod); in_s[nod]=true;
     for(vector <int>::iterator it=G[nod].begin(); it!=G[nod].end(); ++it) {
      if(idx[*it]==-1) dfs(*it), lowlink[nod]=minim(lowlink[nod],lowlink[*it]);
      else if(in_s[*it]==true)
       lowlink[nod]=minim(lowlink[nod],lowlink[*it]);
     }
     if(idx[nod]==lowlink[nod]){
      con.clear();
      int node;
      do{
       con.push_back(node=S.top());
       S.pop(), in_s[node]=false;
      }
      while(node!=nod);
      C.push_back(con);
     }
}
void write(){
     ofstream g("ctc.out");
     g<<C.size()<<"\n";
     for(size_t i=0;i<C.size();++i){
      for(size_t j=0;j<C[i].size();++j)
       g<<C[i][j]<<" ";
      g<<"\n";
     }
      
}
int main(){
    read();
    for(int i=1;i<=n;++i) 
     if(idx[i]==-1) dfs(i);
    write();
    return 0;
}