Cod sursa(job #2464849)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 28 septembrie 2019 23:35:36
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 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);
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> 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();
  }
  cout << ans << "\n";
  for (int i = 1; i <= ans; ++i) {
    for (int v : scc[i]) {
      cout << v << " ";
    }
    cout << "\n";
  }
  return 0;
}