Cod sursa(job #2842683)

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

#define NMAX 100008

using namespace std;

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

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

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;

    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;
            for(int j = 1; j <= n; j ++)
                p[j] = f[j] = 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;
}