Cod sursa(job #2877829)

Utilizator AndreiV03Andrei Voicu AndreiV03 Data 25 martie 2022 13:50:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

int n, m, sol;
vector<vector<int>> G, GT, A;
vector<bool> VC;
stack<int> S;

void dfs_G(int k) {
  VC[k] = 1;
  
  for (auto x : G[k])
    if (VC[x] == 0)
      dfs_G(x);
      
  S.push(k);
}

void dfs_GT(int k) {
  VC[k] = 1;
  A[sol].push_back(k);
  
  for (auto x : GT[k])
    if (VC[x] == 0)
      dfs_GT(x);
}

int main() {
  cin >> n >> m;
  G = GT = A = vector<vector<int>> (n + 1);
  
  for (int i = 1, a, b; i <= m; ++i) {
    cin >> a >> b;
    G[a].push_back(b);
    GT[b].push_back(a);
  }

  VC = vector<bool> (n + 1, 0);
  for (int i = 1; i <= n; ++i)
    if (VC[i] == 0)
      dfs_G(i);

  VC = vector<bool> (n + 1, 0);
  while (!S.empty()) {
    int k = S.top();
    S.pop();
    
    if (VC[k] == 0)
      ++sol, dfs_GT(k);
  }
  
  cout << sol << "\n";
  for (int i = 1; i <= sol; ++i, cout << "\n")
    for (auto x : A[i])
      cout << x << " ";

  cin.close();
  cout.close();
  return 0;
}