Cod sursa(job #3268939)

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

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

const int MAXN = 1e5;
int N, M;
vector<int> G[MAXN + 1];
bool viz[MAXN + 1], inTStack[MAXN + 1];
stack<int> tStack;
vector<vector<int>> ctc;
int gIdx = 0;
int ll[MAXN + 1], idx[MAXN + 1];

void tarjan(int nod) {
    tStack.push(nod);
    inTStack[nod] = 1;
    viz[nod] = 1;
    idx[nod] = ll[nod] = ++gIdx;
    for (const auto& n : G[nod]) {
        if (!viz[n]) {
            tarjan(n);
            ll[nod] = min(ll[nod], ll[n]);
        } else if (inTStack[n]) {
            ll[nod] = min(ll[nod], idx[n]);
        }
    }

    if (ll[nod] == idx[nod]) {
        vector<int> comp;
        comp.push_back(nod);
        while (tStack.top() != nod) {
            comp.push_back(tStack.top());
            inTStack[tStack.top()] = 0;
            tStack.pop();
        }
        tStack.pop();
        ctc.push_back(comp);
    }
}

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