Cod sursa(job #1361949)

Utilizator juniorOvidiu Rosca junior Data 26 februarie 2015 05:26:21
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <iostream>
#include <vector>

#define MAXN 100001

using namespace std;

int n, m, ni, nr;
bool p[MAXN], viz[MAXN], vizt[MAXN];
vector<int> v[MAXN], vt[MAXN], s[MAXN];
ifstream fin("ctc.in");
ofstream fout("ctc.out");

void DFS (int nc) {
  vector<int>::iterator i;
  viz[nc] = true;
  for (i = v[nc].begin(); i != v[nc].end(); ++i)
    if (not viz[*i])
      DFS (*i);
}

void DFSt (int nc) {
  vector<int>::iterator i;
  vizt[nc] = true;
  for (i = vt[nc].begin(); i != vt[nc].end(); ++i)
    if (not vizt[*i])
      DFSt (*i);
}

int main() {
  int i, j, l, c;
  fin >> n >> m;  // Se citeste numarul de noduri si numarul de muchii.
  for (i = 1; i <= m; i++) { // Pentru fiecare muchie
    fin >> l >> c; // Se citesc informatiile despre o muchie.
    v[l].push_back(c);
    vt[c].push_back(l); // vecini in graful transpus
  }
  for (i = 1; i <= n; i++)
    p[i] = true;
  for (i = 1; i <= n; i++)
    if (p[i]) {
      nr++;
      DFS(i);
      DFSt(i);
      for (j = 1; j <= n; j++)
        if (viz[j] and vizt[j]) {
          s[nr].push_back(j); p[j] = false;
        }
      for (j = 1; j <= n; j++)
        viz[j] = vizt[j] = 0;
    }
  fout << nr << '\n';
  for (c = 1; c <= nr; c++) { // c - componenta
    for (n = 0; n <= s[c].size() - 1; n++) // n - nodul
      fout << s[c][n] << ' ';
    fout << '\n';
  }
  return 0;
}