Cod sursa(job #3207915)

Utilizator devilexeHosu George-Bogdan devilexe Data 27 februarie 2024 07:05:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 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];
int N, M;

stack<int> tStack;
bool inTStack[MAXN + 1], viz[MAXN + 1];
int gIdx = 0, idx[MAXN + 1], ll[MAXN + 1];
vector<vector<int> > sol;

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

    if(idx[nod] == ll[nod]) {
        // build scc
        vector<int> comp;
        int exStack;
        do {
            exStack = tStack.top();
            tStack.pop();
            inTStack[exStack] = 0;
            comp.emplace_back(exStack);
        } while(exStack != nod);
        sol.emplace_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);
    fout << sol.size() << '\n';
    for(const auto& comp : sol) {
        for(const auto& x : comp)
            fout << x << ' ';
        fout << '\n';
    }
    return 0;
}