Cod sursa(job #3216676)

Utilizator devilexeHosu George-Bogdan devilexe Data 19 martie 2024 08:01:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 300000;
int N, M;
vector<int> G[MAXN + 1];

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

void read()
{
    fin >> N >> M;
    int a, b;
    while (M--)
    {
        fin >> a >> b;
        G[a].emplace_back(b);
    }
}

void tarjan(int nod)
{
    tStack.emplace(nod);
    inTStack[nod] = 1;
    viz[nod] = 1;
    idx[nod] = ll[nod] = ++gIdx;
    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 (ll[nod] == idx[nod])
    {
        // extract ctc
        int ex;
        vector<int> comp;
        do
        {
            ex = tStack.top();
            tStack.pop();
            inTStack[ex] = 0;
            comp.emplace_back(ex);
        } while (ex != nod);
        comps.emplace_back(comp);
    }
}

void make_ctc()
{
    for (int i = 1; i <= N; ++i)
    {
        if (!viz[i])
            tarjan(i);
    }
}

void print() {
    fout << comps.size() << '\n';
    for(const auto& comp : comps) {
        for(const auto& x : comp) {
            fout << x << ' ';
        }
        fout << '\n';
    }
}

int main()
{
    read();
    make_ctc();
    print();
    return 0;
}