Cod sursa(job #2464850)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 28 septembrie 2019 23:37:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_V = 100005;

int n, m;
int ans;

bool visited[MAX_V];

stack < int > st;
vector < int > G[MAX_V], R[MAX_V];
vector < int > scc[MAX_V];

void dfs(int u) {
  visited[u] = true;
  for (int v : G[u]) {
    if (visited[v] == 0) {
      dfs(v);
    }
  }
  st.push(u);
}

void dfsScc(int u) {
  scc[ans].push_back(u);
  visited[u] = true;
  for (int v : R[u]) {
    if (visited[v] == 0) {
      dfsScc(v);
    }
  }
}

int main() {
  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    G[u].push_back(v);
    R[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i) {
    if (visited[i] == 0) {
      dfs(i);
    }
  }
  memset(visited, 0, sizeof(visited));
  while (st.size() > 0) {
    if (visited[st.top()] == 0) {
      ++ans;
      dfsScc(st.top());
    }
    st.pop();
  }
  printf("%d\n", ans);
  for (int i = 1; i <= ans; ++i) {
    for (int v : scc[i]) {
      printf("%d ", v);
    }
    printf("\n");
  }
  return 0;
}