Cod sursa(job #3371033)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 28 octombrie 2026 12:23:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 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];
vector<vector<int>> comps;
stack<int> stk;

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

void dfs2(int node, vector<int> &comp)
{
    viz[node] = true;
    comp.push_back(node);
    for(int next : trans[node])
    {
        if(viz[next] == true)
            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] == true)
            continue;
        dfs1(node);
    }
    memset(viz, false, sizeof(viz));
    while(!stk.empty())
    {
        int node = stk.top(); stk.pop();
        if(viz[node] == true)
            continue;
        vector<int> comp;
        dfs2(node, comp);
        comps.emplace_back(comp);
    }
    fout << comps.size() << "\n";
    for(const auto &comp : comps)
    {
        for(int node : comp)
            fout << node << " ";
        fout << "\n";
    }

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