Cod sursa(job #3335544)

Utilizator petric_mariaPetric Maria petric_maria Data 22 ianuarie 2026 21:17:51
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

int n, m, x, y;
int ans = 0;
vector <int> v[100005], vt[100005];
vector <int> vis(100005, 0), vist(100005, 0);
vector <int> order;
vector <vector<int>> components;

void dfs1 (int k) {
    vis[k] = 1;
    for (auto x: v[k])
        if (vis[x] == 0)
            dfs1(x);
    order.push_back (k);
}

void dfs2 (int k) {
    vist[k] = 1;
    for (auto x: vt[k])
        if (vist[x] == 0)
            dfs2(x);
    components[ans].push_back (k);
}

int main()
{
    f >> n >> m;
    for (int i=1; i<=m; ++i) {
        f >> x >> y;
        v[x].push_back (y);
        vt[y].push_back (x);
    }

    for (int i=1; i<=n; ++i)
        if (vis[i] == 0)
            dfs1 (i);

    for (int i=order.size()-1; i>=0; --i)
        if (vist [order[i]] == 0) {
            components.push_back ({});
            dfs2 (order[i]);
            ++ans;
        }

    g << ans << '\n';
    for (int i=0; i<ans; ++i) {
        for (int j=components[i].size()-1; j>=0; --j)
            g << components[i][j] << ' ';
        g << '\n';
    }
    return 0;
}