Cod sursa(job #2738622)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 6 aprilie 2021 09:57:06
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m;
vector<int> g[100005], gt[100005];
vector<int> sorted;
bool v[100005];
vector<vector<int> > ctc;

void dfs1(int x) {
    v[x] = true;
    for(auto next: g[x])
        if(!v[next])
            dfs1(next);
    sorted.push_back(x);
}

void dfs2(int x) {
    v[x] = true;
    ctc.back().push_back(x);
    for(auto next: gt[x])
        if(!v[next])
            dfs2(next);
}

int main() {
    fin >> n >> m;
    while(m--) {
        int u, v;
        fin >> u >> v;
        g[u].push_back(v);
        gt[v].push_back(u);
    }

    dfs1(1);

    for(int i = 1; i <= n; i++) v[i] = false;
    for(int i = sorted.size()-1; i >= 0; i--) {
        int x = sorted[i];
        if(!v[x]) {
            ctc.push_back({});
            dfs2(x);
        }
    }
    fout << ctc.size() << '\n';
    for(auto c: ctc) {
        for(auto x: c)
            fout << x << ' ';
        fout << '\n';
    }
}