Cod sursa(job #3266177)

Utilizator Andercau_VasileAndercau Vasile Andercau_Vasile Data 6 ianuarie 2025 12:12:56
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
using namespace std;

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

#define NMAX 100005

vector<int> G[NMAX], GT[NMAX];
vector<int> CTC[NMAX];
bool viz1[NMAX], viz2[NMAX];
int ord[NMAX];
int nr;
int nrc;

void dfs1(int nod) {
    viz1[nod] = 1;

    for (auto it : G[nod]) {
        if (!viz1[it]) {
            dfs1(it);
        }
    }

    ord[++nr] = nod;
}

void dfs2(int nod) {
    viz2[nod] = 1;
    CTC[nrc].push_back(nod);

    for (auto it : GT[nod]) {
        if (!viz2[it]) {
            dfs2(it);
        }
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    while (m--) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }

    for (int i = 1; i <= n; ++i) {
        if (!viz1[i]) {
            dfs1(i);
        }
    }

    for (int i = n ; i >= 1; --i) {
        if (!viz2[ord[i]]) {
            nrc++;
            dfs2(ord[i]);
        }
    }

    fout << nrc << '\n';
    for (int i = 1; i <= nrc; ++i) {
        for (auto it : CTC[i]) {
            fout << it << ' ';
        }
        fout << '\n';
    }
    return 0;
}