Cod sursa(job #526947)

Utilizator emilian.mironEmilian Miron emilian.miron Data 29 ianuarie 2011 23:47:16
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

int N;
vector<vector<int> > adj;
vector<vector<int> > rev;
vector<vector<int> > sol;
vector<bool> viz;
stack<int> finished;

void dfs1(int nod) {
  if (viz[nod]) return;
  viz[nod] = true;
  for (int i = 0; i < adj[nod].size(); ++i) {
    dfs1(adj[nod][i]);
  }
  finished.push(nod);
}

void dfs2(int nod, vector<int> &csol) {
  if (!viz[nod]) return;
  csol.push_back(nod);
  viz[nod] = false;
  for (int i = 0; i < rev[nod].size(); ++i) {
    dfs2(rev[nod][i], csol);
  }
}

int main(void) {
  int M;
  freopen ("ctc.in", "rt", stdin);
  freopen ("ctc.out", "wt", stdout);

  scanf("%d %d", &N, &M);
  adj.resize(N + 1);
  rev.resize(N + 1);
  viz.resize(N + 1);
  while (M--) {
    int x, y;
    scanf ("%d %d", &x, &y);
    adj[x].push_back(y);
    rev[y].push_back(x);
  }

  for (int i = 1; i <= N; ++i) dfs1(i);
  while (!finished.empty()) {
    if (viz[finished.top()]) {
      vector<int> csol;
      dfs2(finished.top(), csol);
      sol.push_back(csol);
    }
    finished.pop();
  }

  printf ("%d\n", (int)sol.size());
  for (int i = 0; i < sol.size(); ++i) {
    for (int j = 0; j < sol[i].size(); ++j) {
      printf ("%s%d", j ? " " : "", sol[i][j]);
    }
    printf("\n");
  }

  return 0;
}