Cod sursa(job #640638)

Utilizator attila3453Geiszt Attila attila3453 Data 26 noiembrie 2011 11:03:45
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

int f[100001], s[200001], t, n, m;
bool viz[100001];
//fstream fi("dffinal2.in",ios::in);
ifstream fi("ctc.in");
ofstream fo("ctc.out");
vector <int> v[100001], vt[100001];

// In s retinem nodurile sortate dupa timpii finali.
void dffinal(int i) {                              //fo << "i = " << i << endl;
  int c;

  viz[i] = true; t++;                              //         fo << t << endl;
  for (c = 0; c < v[i].size(); c++)
    if (!viz[v[i][c]])    // Nu a fost vizitat.
      dffinal(v[i][c]);
  t++; f[i] = t; s[t] = i;			      				//			fo << "f[" << i << "] = " << t << endl;
}
void dfsc(int i) {
  int c;

  fo << i << ' ';
  viz[i] = true;                 // Il consideram vizitat.
  for (c = 0; c < vt[i].size(); c++)
    if (!viz[vt[i][c]])          // nu a fost vizitat.
      dfsc(vt[i][c]);            // parcurgem in adancime.
}
int main() {
  int x, y, i, nc, l, c;

  fi >> n >> m;
  for (i = 1; i <= m; i++) {
    fi >> x >> y;
    v[x].push_back (y);
    vt[y].push_back (x);
  }
  t = 0;
  for(i = 1;i<=n;i++)
    if(!viz[i])
      dffinal(i);

  memset(viz, 0, 100001);

  for (l = t-1; l >= 0; l--) { // Parcurgem sirul sortat al nodurilor.
    if (s[l]) {              // S-ar putea ca locului l sa nu ii corespunda un nod.
      nc = s[l];             // nodul curent
      if (!viz[nc]) {        // Nu a fost vizitat.
        dfsc(nc);            // Parcurgem o componenta.
        fo << '\n';
      }
    }
  }

  return 0;
}