Cod sursa(job #3374889)

Utilizator StanescuMateiStanescu Matei StanescuMatei Data 9 noiembrie 2026 17:53:57
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adj;
vector<vector<int>> adjT;
vector<int> viz;
vector<int> vizT;
vector<int> apartineCtc;
vector<vector<int>> ctc;

void dfs(int start) {
  viz[start] = 1;

  for (int i = 0; i < adj[start].size(); i++) {
    int next = adj[start][i];
    if (!viz[next]) {
      dfs(next);
    }
  }
}

void dfsT(int start, int group) {
  vizT[start] = 1;

  if (viz[start]) {
    ctc[group].push_back(start);
    apartineCtc[start] = 1;
  }

  for (int i = 0; i < adjT[start].size(); i++) {
    int next = adjT[start][i];
    if (!vizT[next]) {
      dfsT(next, group);
    }
  }
}

int main() {
  ifstream fin("ctc.in");
  ofstream fout("ctc.out");

  int n, m;
  fin >> n >> m;

  viz.resize(n + 5);
  vizT.resize(n + 5);
  ctc.resize(n + 5);
  adj.resize(n + 5);
  adjT.resize(n + 5);
  apartineCtc.resize(n + 5);

  for (int i = 0; i < m; i++) {
    int x, y;
    fin >> x >> y;

    adj[x].push_back(y);
    adjT[y].push_back(x);
  }

  int ctcCount = 0;
  for (int i = 1; i <= n; i++) {
    if (!apartineCtc[i]) {
      dfs(i);
      dfsT(i, i);

      viz.assign(n + 5, 0);
      vizT.assign(n + 5, 0);

      ctcCount++;
    }
  }

  fout << ctcCount << "\n";
  for (int i = 1; i <= n; i++) {
    if (ctc[i].size() == 0)
      continue;

    for (const auto &nod : ctc[i]) {
      fout << nod << " ";
    }
    fout << "\n";
  }
}