Cod sursa(job #1476420)

Utilizator salam1Florin Salam salam1 Data 25 august 2015 09:16:21
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int NMAX = 100505;
int n, m, st[NMAX], r;
vector<int> G[NMAX], GT[NMAX];
vector<vector<int>> sol;
bool mark[NMAX];

void read() {
  scanf("%d%d", &n, &m);
  int x, y;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    G[x].push_back(y); GT[y].push_back(x);
  }
}

void dfs1(int node) {
  mark[node] = true;
  for (auto y: G[node]) {
    if (!mark[y]) {
      dfs1(y);
    }
  }
  st[++r] = node;
}

void dfs2(int node, vector<int>& sol) {
  mark[node] = true;
  sol.push_back(node);
  for (auto y: GT[node]) {
    if (!mark[y]) {
      dfs2(y, sol);
    }
  }
}

void solve() {
  // topological sort of the final DAG
  for (int i = 1; i <= n; i++)
    if (!mark[i])
      dfs1(i);
  
  // at each step we take the node with the highest POST ;
  // a source node (no incoming edges) in the final DAG
  // => a sink node in the final DAG transposed =>
  // if we do a dfs on it, it will visit all the nodes in its
  // connected component, but it won't visit any others
  memset(mark, false, sizeof(mark));
  for (int i = r; i >= 1; i--) {
    if (!mark[st[i]]) {
      sol.push_back(vector<int>());
      dfs2(st[i], sol.back());
    }
  }
  
  printf("%d\n", (int)sol.size());
  for (auto entry: sol) {
    for (size_t i = 0; i < entry.size(); i++) {
      if (i > 0) printf(" ");
      printf("%d", entry[i]);
    }
    printf("\n");
  }
}

int main() {
  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);
  
  read();
  solve();
  return 0;
}