Cod sursa(job #2842695)

Utilizator SmauSmau George Robert Smau Data 1 februarie 2022 12:47:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

#define NMAX 100008

using namespace std;

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

vector <vector <int>> G, GT;
vector <bool> used;
vector <int> V;

vector <vector <int>> ans;
vector <int> TC;

int n, m;

void DFS(int node) {
    used[node] = true;
    for(auto x : G[node])
        if(!used[x]) DFS(x);

    V.push_back(node);
}

void DFST(int node) {
    used[node] = true;
    TC.push_back(node);

    for(auto x : GT[node])
        if(!used[x]) DFST(x);
}

int main() {
    fin >> n >> m;

    G = GT = vector <vector <int>> (n + 1);
    used = vector <bool> (n + 1, false);

    for(int i = 1; i <= m; i ++) {
        int x, y; fin >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }

    for(int i = 1; i <= n; i ++)
        if(!used[i]) DFS(i);

    used = vector <bool> (n + 1, false);
    for(int i = V.size() - 1; i >= 0; i --)
        if(!used[V[i]]) {
            TC = vector <int> (0);
            DFST(V[i]);
            ans.push_back(TC);
        }

    fout << ans.size() << '\n';
    for(auto x : ans) {
        for(auto y : x) fout << y << ' ';
        fout << '\n';
    }

    return 0;
}