Cod sursa(job #3243555)

Utilizator StefannnnnStefan Stefannnnn Data 19 septembrie 2024 14:21:54
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 3e5 + 1;

vector<int> adj[nmax], inv[nmax], ord, comp[nmax];

bool f[nmax];
int root[nmax];

void dfs1(int i) {
  f[i] = 1;
  for(auto it : inv[i]) {
    if(f[it] == 0) {
      dfs1(it);
    }
  }
  ord.push_back(i);
}

void dfs2(int i, int r) {
  f[i] = 1;
  root[i] = r;
  for(auto it : adj[i]) {
    if(!f[it]) {
      dfs2(it, r);
    }
  }
}

int main() {
  ifstream cin("ctc.in");
  ofstream cout("ctc.out");
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    inv[b].push_back(a);
  }
  for(int i = 1; i <= n; i++) {
    if(!f[i]) {
      dfs1(i);
    }
  }
  memset(f, 0, sizeof(f));
  reverse(ord.begin(), ord.end());
  int ans = 0;
  for(auto it : ord) {
    if(!f[it]) {
      ans++;
      dfs2(it, it);
    }
  }
  for(int i = 1; i <= n; i++) {
    comp[root[i]].push_back(i);
  }
  cout << ans << '\n';
  for(int i = 1; i <= n; i++) {
    for(auto it : comp[i]) {
      cout << it << " ";
    }
    if(comp[i].size() > 0) {
      cout << '\n';
    }
  }
  return 0;
}