Cod sursa(job #2078404)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 29 noiembrie 2017 15:33:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

vector<int>G1[100005];
vector<int>G2[100005];
vector<int>sol[100005];
int lista[100005];
bool viz[100005];
int k;

void dfs1(int node) {
  viz[node] = 1;
  for (auto it:G1[node])
    if (!viz[it])
      dfs1(it);
  lista[++k] = node;
}

void dfs2(int node) {
  viz[node] = 0;
  sol[k].push_back(node);
  for (auto it:G2[node])
    if (viz[it])
      dfs2(it);
}

int main() {
  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);

  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    G1[u].push_back(v);
    G2[v].push_back(u);
  }

  for (int i = 1; i <= n; ++i)
    if (!viz[i])
      dfs1(i);
  k = 0;
  for (int i = n; i >= 1; --i) {
    if (viz[lista[i]]) {
      k++;
      dfs2(lista[i]);
    }
  }

  printf("%d\n", k);
  for (int i = 1; i <= k; ++i) {
    for (auto it:sol[i])
      printf("%d ", it);
    printf("\n");
  }

  return 0;
}