Cod sursa(job #3299111)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 4 iunie 2025 16:40:31
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
using namespace std;
const int N = 1e5 + 9;

const string TASK("ctc");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout

int n, m;
vvi G(N), IG(N);
vector<int> stk;

bool v1[N];
void Dfs1(int x)
{
    v1[x] = true;
    stk.pb(x);
    for(auto y : G[x])
        if(!v1[y])
            Dfs1(y);
}

bool v2[N];
void Dfs2(int x, vi& res)
{
    v2[x] = true;
    res.pb(x);
    for(auto y : IG[x])
        if(!v2[y])
            Dfs2(y, res);
}

int main()
{
    cin >> n >> m;

    int x, y;
    FOR(i, 1, m)
    {
        cin >> x >> y;
        G[x].pb(y);
        IG[y].pb(x);
    }

    FOR(i, 1, n)
        if(!v1[i])
            Dfs1(i);

    vvi ctc;
    while(!stk.empty())
    {
        int x = stk.back();
        stk.pop_back();

        if(v2[x])continue;

        ctc.pb({});
        Dfs2(x, ctc.back());
    }

    cout << ctc.size() << '\n';
    for(auto i : ctc)
    {
        for(auto j : i)cout << j << ' ';
        cout << '\n';
    }
    return 0;
}