Cod sursa(job #3371040)

Utilizator Cristian_NegoitaCristian Negoita Cristian_Negoita Data 28 octombrie 2026 12:44:23
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX = 1e5 + 1;
int n, m, in[NMAX], low[NMAX], timer = 0;
bool viz[NMAX], on_stack[NMAX];
vector<int> adj[NMAX];
vector<vector<int>> comps;
stack<int> stk;

void dfs(int node)
{
    in[node] = low[node] = ++timer;
    stk.push(node); on_stack[node] = true;
    viz[node] = true;
    for(int next : adj[node])
    {
        if(viz[next] == false)
        {
            dfs(next);
            low[node] = min(low[node], low[next]);
        }
        else if(on_stack[next] == true)
            low[node] = min(low[node], in[next]);
    }
    if(in[node] == low[node])
    {
        vector<int> comp;
        while(!stk.empty())
        {
            int u = stk.top(); stk.pop();
            on_stack[u] = false;
            comp.push_back(u);
            if(u == node)
                break;
        }
        comps.emplace_back(comp);
    }
}

int main()
{
    fin >> n >> m;
    while(m--)
    {
        int u, v;
        fin >> u >> v;
        adj[u].push_back(v);
    }
    for(int node = 1; node <= n; node++)
    {
        if(viz[node] == true)
            continue;
        dfs(node);
    }
    fout << comps.size() << "\n";
    for(const auto &comp : comps)
    {
        for(int node : comp)
            fout << node << " ";
        fout << "\n";
    }

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