Cod sursa(job #3225665)

Utilizator MoolampMoolamp Moolamp Data 18 aprilie 2024 14:17:38
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 1e5 + 5;

bool viz[NMAX];
int n, m, nrcomp;
vector<int> v[NMAX], rev[NMAX], comp[NMAX];
stack<int> ord;

void dfs (int x)
{
  viz[x] = true;
  for (auto u : v[x])
    if (!viz[u])
      dfs(u);
  ord.push(x);
}

void dfs2 (int x)
{
  comp[nrcomp].push_back(x);
  viz[x] = true;
  for (auto u : rev[x])
    if (!viz[u])
      dfs2(u);
}

signed main ()
{
  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  while (m--)
  {
    int x, y; cin >> x >> y;
    v[x].push_back(y);
    rev[y].push_back(x);
  }
  dfs(1);
  memset(viz, false, sizeof(viz));
  while (ord.size())
  {
    int x = ord.top();
    ord.pop();
    if (viz[x])
      continue;
    ++nrcomp;
    dfs2(x);
  }
  cout << nrcomp << '\n';
  for (int i = 1; i <= nrcomp; i++, cout << '\n')
    for (auto x : comp[i])
      cout << x << ' ';
}