Cod sursa(job #3302751)

Utilizator andrei.nNemtisor Andrei andrei.n Data 10 iulie 2025 16:53:59
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;

vector<int> v1[100005], v2[100005];
int depth[100005];
int ord[100005];
int idx;
vector<int> comp[100005];

void dfs1(int node)
{
    for(auto &son : v1[node])
        if(!depth[son])
        {
            depth[son] = depth[node] + 1;
            dfs1(son);
        }
    ord[++idx] = node;
}

void dfs2(int node, int color)
{
    for(auto &son : v2[node])
        if(!depth[son])
        {
            depth[son] = depth[node];
            dfs2(son, color);
        }
}

signed main()
{
    ifstream fin ("ctc.in");
    ofstream fout ("ctc.out");
    ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
    int n, m; fin>>n>>m;
    while(m--)
    {
        int a, b; fin>>a>>b;
        if(a == b) continue;
        v1[a].push_back(b);
        v2[b].push_back(a);
    }
    for(int i=1; i<=n; ++i)
        if(!depth[i])
        {
            depth[i] = 1;
            dfs1(i);
        }
    reverse(ord+1, ord+n+1);
    for(int i=1; i<=n; ++i)
        depth[i] = 0;
    int color = 0;
    for(int i=1; i<=n; ++i)
        if(!depth[ord[i]])
        {
            depth[ord[i]] = ++color;
            dfs2(ord[i], color);
            comp[color].push_back(ord[i]);
        }
        else
            comp[depth[ord[i]]].push_back(ord[i]);
    fout<<color<<'\n';
    for(int i=1; i<=color; ++i, fout<<'\n')
        for(auto &j : comp[i])
            fout<<j<<' ';
    return 0;
}