Cod sursa(job #255480)

Utilizator MciprianMMciprianM MciprianM Data 9 februarie 2009 20:43:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
#include<vector>
using namespace std;
#define maxn 100009
vector<int> G[maxn], GT[maxn];
vector< vector<int> > Comp;
vector<int> linie;
int viz[maxn], st[maxn];
int n, m, t,nrctc;
int df1(int nod){
  viz[nod]=1;
  vector<int>::iterator it;
  for(it=G[nod].begin();it!=G[nod].end();++it)
    if(!viz[*it])
      df1(*it);
  t++;
  st[t]=nod;
}
void topo(){
  int i;
  for(i=1;i<=n;i++)
    if(!viz[i])
      df1(i);
}
void df2(int nod){
   int i;
   vector<int>::iterator it;
   viz[nod]=1;
   for(it=GT[nod].begin();it!=GT[nod].end();++it)
     if(!viz[*it]){
       linie.push_back(*it);
       df2(*it);
     }
}
int main(){
  int i, x, y;
  ifstream f("ctc.in");
  f>>n>>m;
  for(i=0;i<m;i++){
    f>>x>>y;
    G[x].push_back(y);
    GT[y].push_back(x);
  }
  f.close();
  topo();
  for(i=1;i<=n;i++)
    viz[i]=0;
  for(i=t;i>0;i--)
     if(!viz[st[i]]){
       linie.push_back(st[i]);
       df2(st[i]);
       Comp.push_back(linie);
       linie.resize(0);
       ++nrctc;
     }
  vector<int>::iterator it;
  ofstream g("ctc.out");
  g<<nrctc<<'\n';
  for(i=0;i<nrctc;i++){
    for(it=Comp[i].begin();it!=Comp[i].end();++it)
      g<<*it<<' ';
    g<<'\n';
  }
  g.close();
  return 0;
}