Cod sursa(job #3271063)

Utilizator darian4444Verniceanu Darian darian4444 Data 25 ianuarie 2025 09:53:50
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

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

int N,M,i,j,a,b,ctc_cur;
vector<int> G[100005],rG[100005];
int ctc[100005];
deque<int> s;
bool v[100005];
vector<int> ans[100005];

void dfs(int k){
    v[k] = 1;

    for (auto next_k : G[k])
        if (!v[next_k])
            dfs(next_k);
    s.push_front(k);
}

void kosaraju(int k){
    ctc[k] = ctc_cur;
    ans[ctc_cur].push_back(k);

    for (auto next_k : rG[k])
        if (!ctc[next_k])
            kosaraju(next_k);
}

int main()
{
    fin >> N >> M;

    for (i = 1;i <= M;i++){
        fin >> a >> b;

        G[a].push_back(b);
        rG[b].push_back(a);
    }

    for (i = 1;i <= N;i++)
        if (!v[i])
            dfs(i);

    for (auto k : s)
        if (!ctc[k]){
            ctc_cur++;
            kosaraju(k);
        }

    fout << ctc_cur << "\n";

    for (i = 1;i <= 100000;i++)
        if (ans[i].size() == 0)
            break;
        else{
            for (auto node : ans[i])
                fout << node << " ";
            fout << "\n";
        }

    return 0;
}