Cod sursa(job #3268938)

Utilizator devilexeHosu George-Bogdan devilexe Data 18 ianuarie 2025 09:42:23
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAXN = 1e5;
vector<int> G[MAXN + 1], Gt[MAXN + 1];
stack<int> kStack;
bitset<MAXN + 1> viz;
int N, M;

void dfs(int nod) {
    viz[nod] = 1;
    for (const auto& x : G[nod])
        if (!viz[x])
            dfs(x);
    kStack.push(nod);
}

vector<vector<int>> ctc;
vector<int> comp;
void dfst(int nod) {
    viz[nod] = 1;
    for (const auto& x : Gt[nod]) {
        if (!viz[x])
            dfst(x);
    }
    comp.push_back(nod);
}

int main() {
    fin >> N >> M;
    int a, b;
    while (M--) {
        fin >> a >> b;
        G[a].push_back(b);
        Gt[b].push_back(a);
    }
    for (int i = 1; i <= N; i++) {
        if (!viz[i])
            dfs(i);
    }
    viz.reset();
    while (!kStack.empty()) {
        if (!viz[kStack.top()]) {
            comp = vector<int>();
            dfst(kStack.top());
            ctc.push_back(comp);
        }
        kStack.pop();
    }
    fout << ctc.size() << '\n';
    for (const auto& c : ctc) {
        for (const auto& x : c)
            fout << x << ' ';
        fout << '\n';
    }
    return 0;
}