Cod sursa(job #3372301)

Utilizator aspaNadu Tudor aspa Data 3 noiembrie 2026 01:44:36
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
#define MAX 100001
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int N, M, id = 0;
vector<int> A[MAX];
int ids[MAX], low[MAX];
bool onStack[MAX];
stack<int> s;
vector<vector<int>> comps;

void dfs(int k) {
    s.push(k);
    onStack[k] = true;
    ids[k] = low[k] = id++;

    for (int to : A[k]) {
        if (ids[to] == -1) {
            dfs(to);
            low[k] = min(low[k], low[to]);
        }
        else if (onStack[to]) {
            low[k] = min(low[k], ids[to]);
        }
    }

    if (ids[k] == low[k]) {
        vector<int> comp;
        while (true) {
            int node = s.top(); 
            s.pop();

            onStack[node] = false;
            comp.push_back(node);

            if (node == k) 
                break;
        }

        comps.push_back(comp);
    }
}

int main() {
    fin >> N >> M;
    int x, y;

    for (int i = 0; i < M; i++) {
        fin >> x >> y;
        A[x].push_back(y);
    }

    memset(ids, -1, sizeof(ids));

    for (int i = 1; i <= N; i++)
        if (ids[i] == -1) 
            dfs(i);

    fout << comps.size() << "\n";

    for (auto &c : comps) {
        for (int v : c) 
            fout << v << " ";
        fout << "\n";
    }
}