Cod sursa(job #3207294)

Utilizator TrifoitaBejenescu-Babusanu Stefan Trifoita Data 25 februarie 2024 19:07:51
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
/*

Fie un graf orientat G = (V, E), memorat prin intermediul matricei de adiacenta, si un nod i.
Afisati componenta tare conexa careia ii apartine acesta.

Ex:
5
1 2
1 4
2 3
3 1
4 5
5 4

Input: nodul 1: 1, 2, 3
       nodul 2: 1, 2, 3
       nodul 3: 1, 2, 3
       nodul 4: 4, 5
       nodul 5: 4, 5

*/

#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, nr_componente = 0, matrix[10001][10001];
int pred[1001], succ[1001], marcat[1001];
int componente[10001][10001];

void citire() {
  fin >> n >> m;
  int x, y;
  for (int i = 1; i <= m; i++) {
    fin >> x >> y;
    matrix[x][y] = 1;
  }
}

void dfs_succ(int node) {
  succ[node] = 1;
  for (int i = 1; i <= n; i++)
    if (matrix[node][i] && !succ[i])
      dfs_succ(i);
}

void dfs_prec(int node) {
  pred[node] = 1;
  for (int i = 1; i <= n; i++)
    if (matrix[i][node] && !pred[i])
      dfs_prec(i);
}

void reset() {
  for (int i = 1; i <= n; i++) succ[i] = pred[i] = 0;
}

void tare_conex(int node) {
  nr_componente++;
  dfs_prec(node);
  dfs_succ(node);
  for (int i = 1; i <= n; i++)
    if (succ[i] && pred[i]) {
      componente[nr_componente][i] = 1;
      marcat[i] = 1;
    }
  reset();
}

int main() {
  citire();
  for (int node = 1; node <= n; node++)
    if (!marcat[node])
      tare_conex(node);
  fout << nr_componente << '\n';
  for (int i = 1; i <= nr_componente; i++) {
    for (int j = 1; j <= n; j++)
      if (componente[i][j] == 1)
        fout << j << " ";
    fout << '\n';
  }
  return 0;
}