Cod sursa(job #243608)

Utilizator MciprianMMciprianM MciprianM Data 13 ianuarie 2009 18:05:25
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
#define MAXN 50900
vector<int> g[MAXN],gt[MAXN];
//g - graful dat, gt - graful transpus grafului g
int n, m;
//n - nr noduri; m - nr muchii
int nrctc;
//nrctc - nr de componente tare conexe
int fol[MAXN];
bool pls[MAXN],mins[MAXN];
//fol[i]-un nr natural <=n
//daca fol[i]==0 nodul i nu a fost folosit inca intr-o comp t conexa
// daca fol[i]!=0 atunci nodul i a fost folosit in comp t conexa fol[i];

void df1(int nod){
   pls[nod]=1;
   vector<int>::iterator it;
   for(it=g[nod].begin();it!=g[nod].end();++it)
     if(!pls[*it]&&!fol[*it])
       df1(*it);
}

void df2(int nod){
   mins[nod]=1;
   vector<int>::iterator it;
   for(it=gt[nod].begin();it!=gt[nod].end();++it)
     if(!mins[*it]&&!fol[*it])
       df2(*it);
}

int main(){
  int i, x, y, j;
  //citire date
  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();

  for(i=1; i<=n; i++){
     if(!fol[i]){
          df1(i);
          df2(i);
        nrctc++;
        for(j=1;j<=n;j++)
          if(pls[j]&&mins[j])
            fol[j]=nrctc;
        memset(pls,0,sizeof(pls));
        memset(mins,0,sizeof(mins));
     }
  }

  ofstream g("ctc.out");
  g<<nrctc<<'\n';
  for(i=1;i<=nrctc;i++){
    for(j=1;j<=n;j++)
      if(fol[j]==i)
        g<<j<<' ';
    g<<'\n';
  }
  g.close();
  return 0;
}