Cod sursa(job #3319705)

Utilizator iuliarusuIulia Rusu iuliarusu Data 2 noiembrie 2025 18:52:52
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb

#include <bits/stdc++.h>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> G[100001], GT[100001];
vector<int> ctc[100001];
int viz1[100001], viz2[100001], nr;
vector <int> v;

void dfs1(int nod) {
    viz1[nod] = true;
    for (int vecin: G[nod])
        if (!viz1[vecin]) {
            dfs1(vecin);
        }
    v.push_back(nod);
}
void dfs2(int nod) {
    viz2[nod] = 1;
    ctc[nr].push_back(nod);
    for (int vecin: GT[nod])
        if (!viz2[vecin]) {
            dfs2(vecin);
        }
}
int main() {
    int n, m;
    f >> n >> m;
    for (int i=1; i<=m; i++) {
        int a, b;
        f >> a >> b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }
    for (int i=1; i<=n; i++)
        if (!viz1[i])
            dfs1(i);

    for (int i=1; i<=n; i++)
        if (!viz2[v[i]]) {
            nr++;
            dfs2(v[i]);
        }
    g << nr << "\n";
    for (int i=1; i<=nr; i++) {
        for (int nod: ctc[i]) {
            g << nod << " ";
        }
        g << "\n";
    }
    return 0;
}