Cod sursa(job #2926067)

Utilizator PatrascuAdrian1Patrascu Adrian Octavian PatrascuAdrian1 Data 16 octombrie 2022 20:16:15
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
/**
    O metoda de a gasi CTC ale unui graf este
algoritmul lui Kosaraju care se bazeaza pe parcurgerile DFS
ale grafului G dat si ale lui G transpus (Gt).
    In timpul parcurgerii lui G inseram varfurile vizitate
intr-o stiva. Parcurgand stiva, ne aventuram in Gt cu alte
DFS-uri, alipind la fiecare CTC varfurile parcurse din varful curent
al stivei in parcurgerea respectiva. Varfurile se elimina
din stiva inainte de a fi verificate drept canditat pentru radacina
arborelui construit de fiecare DFS in Gt.
*/

#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 1e5 + 5;
vector<int> ans[Nmax], G[Nmax], Gt[Nmax];
stack<int> S;
bool seen[Nmax];
int ctc;

void dfs_1(int node)
{
    seen[node] = 1;
    for(auto i : G[node])
        if(!seen[i])
            dfs_1(i);
    S.push(node);
}

void dfs_2(int node)
{
    seen[node] = 1;
    ans[ctc].push_back(node);
    for(auto i : Gt[node])
        if(!seen[i])
            dfs_2(i);
}

int main()
{
    int N, M;
    in >> N >> M;
    while(M--)
    {
        int x, y;
        in >> x >> y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    for(int i = 1; i <= N; ++i)
        if(!seen[i])
            dfs_1(i);
    memset(seen, 0, sizeof(seen));
    while(!S.empty())
    {
        int node = S.top();
        S.pop();
        if(!seen[node])
        {
            ctc++;
            dfs_2(node);
        }
    }
    out << ctc << '\n';
    for(int i = 1; i <= ctc; ++i)
    {
        for(auto j : ans[i])
            out << j << " ";
        out << '\n';
    }
    return 0;
}