Cod sursa(job #3341886)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 21 februarie 2026 14:08:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 1e5 + 1;
int n, m;
bool viz[NMAX];
vector<int> adj[NMAX], trans[NMAX], stk;
vector<vector<int>> comps;

void dfs1(int node)
{
    viz[node] = true;
    for(int next : adj[node])
    {
        if(viz[next])
            continue;
        dfs1(next);
    }
    stk.push_back(node);
}

void dfs2(int node, vector<int> &comp)
{
    viz[node] = true;
    comp.push_back(node);
    for(int next : trans[node])
    {
        if(viz[next])
            continue;
        dfs2(next, comp);
    }
}

int main()
{
    fin >> n >> m;
    while(m--)
    {
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
        trans[v].push_back(u);
    }
    for(int node = 1; node <= n; node++)
    {
        if(viz[node])
            continue;
        dfs1(node);
    }
    reverse(stk.begin(), stk.end());
    memset(viz, false, sizeof(viz));
    for(int node : stk)
    {
        if(viz[node])
            continue;
        vector<int> comp;
        dfs2(node, comp);
        comps.emplace_back(comp);
    }
    fout << comps.size() << "\n";
    for(auto &comp : comps)
    {
        for(int node : comp)
            fout << node << " ";
        fout << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}