Cod sursa(job #2842682)

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

using namespace std;

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

vector <vector <int>> G, GT;
vector <bool> p, f;
vector <int> ctc;

int n, m;

void DFS(int node) {
    p[node] = true;

    for(auto x : G[node])
        if(!p[x]) DFS(x);
}

void DFST(int node) {
    f[node] = true;

    for(auto y : GT[node])
        if(!f[y]) DFST(y);
}

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

    G = GT = vector <vector <int>> (n + 1);
    ctc = vector <int> (n + 1, 0);

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

    vector <vector <int>> ans;
    for(int i = 1; i <= n; i ++)
        if(ctc[i] == 0) {
            vector <int> TC;
            p = f = vector <bool> (n + 1, false);

            DFS(i); DFST(i);

            for(int j = 1; j <= n; j ++)
                if(p[j] && f[j]) {
                    TC.push_back(j);
                    ctc[j] = ans.size() + 1;
                }

            ans.push_back(TC);
        }

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

    return 0;
}