Cod sursa(job #2928892)

Utilizator cilteaioanaIoana C cilteaioana Data 24 octombrie 2022 01:58:51
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb

#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, y, x, viz[100000], nrComp;
vector<vector<int>> lista, transp, comp;
vector<int> s, v;

void dfs1(int x) {
    viz[x] = 1;
    for (auto i : lista[x])
        if (!viz[i]) dfs1(i);
    s.push_back(x);
}

void dfs2(int x) {
    viz[x] = 0;
    comp[nrComp].push_back(x);
    for (auto i : transp[x])
        if (viz[i])
            dfs2(i);
}

int main() {
    fin >> n >> m;
    lista = transp = vector<vector<int>>(n);
    for (int i = 0; i < m; i++) {
        fin >> x >> y;
        lista[x - 1].push_back(y - 1);
        transp[y - 1].push_back(x - 1);
    }

    for (int i = 0; i < n; i++)
        if (!viz[i]) dfs1(i);

    while (!s.empty()) {
        x = s.back();
        s.pop_back();
        if (viz[x]) {
            comp.push_back(v);
            dfs2(x);
            nrComp++;
        }
    }

    fout << nrComp << '\n';
    for (auto v : comp) {
        for (auto i : v) fout << i + 1 << " ";
        fout << '\n';
    }
}