Cod sursa(job #671456)

Utilizator levaionutLeva Ionut levaionut Data 31 ianuarie 2012 15:23:14
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
// http://infoarena.ro/problema/ctc

#include <fstream>

using namespace std;

int n, m, ni, a[2000][2000], t[2000][2000], v[2000], vt[2000], nr, s[2000][2000];
bool p[2000];
ifstream fi("ctc.in");
ofstream fo("ctc.out");

void DFS (int nc) {
  int i;

  for (i = 1; i <= n; i++) // pentru fiecare nod
    if (a[nc][i] == 1 and v[i] == 0) {// i este vecin nevizitat al nodului curent?
      v[i] = 1;// Marcam i ca fiind vizitat.
      DFS(i);// Continuam parcurgerea in adancime.
    }
}

void DFSt (int nc) { // nodul curent
  int i;

  for (i = 1; i <= n; i++) // pentru fiecare nod
    if (t[nc][i] == 1 and vt[i] == 0) {// i este vecin nevizitat al nodului curent?
      vt[i] = 1;// Marcam i ca fiind vizitat.
      DFSt(i);// Continuam parcurgerea in adancime.
    }
}

int main() {
  int i, j, l, c;

  fi >> n >> m; // Se citeste numarul de noduri si numarul de muchii.
  for (i = 1; i <= m; i++) { // Pentru fiecare muchie
    fi >> l >> c; // Se citesc informatiile despre o arc.
    a[l][c] = 1; t[c][l] = 1; // Se actualizeaza matricea de adiacenta/
  }
   for(i=1;i<=n;i++)
   p[i]=true;// Toate nodurile sunt prezente.
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)// Pentru fiecare nod prezent
    if(p[i] and a[i][j]==1 and t[i][j]==1){// Parcurgem in adancime in graful initial si cel transpus.
        s[i][j]=1; // Retinem nodurile din componenta tare conexa curenta.
        vt[i]=v[i]=0; // Reinitializam vectorii care arata daca nodurile au fost vizitate.
        fo<<i<<' '; // Afisam componentele.
    }

  return 0;
}