Cod sursa(job #3124944)

Utilizator Dani111Gheorghe Daniel Dani111 Data 30 aprilie 2023 18:20:41
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int>G[100001];
vector<int>GT[100001];
vector<int>S;
vector<int>V(100001, false);
vector<int>VT(100001, false);
vector<int>conexe[100001];
int n, m, maxx, cnt;
void citire() {
    f >> n >> m;
    for(int i = 1; i <= m; i++) {
        int x, y;
        f >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}
void dfs(int node) {
    V[node] = true;
    for(auto i : G[node]) {
        if(!V[i]) dfs(i);
    }
    S.push_back(node);
}
void dfs1(int node) {
    VT[node] = true;
    conexe[cnt].push_back(node);
    for(auto i : GT[node]) {
        if(!VT[i]) dfs1(i);
    }
}
void kosaraju() {
    for(int i = 1; i <= n; i++) {
        if(!V[i]) dfs(i);
    }
    for(vector<int>::reverse_iterator it = S.rbegin(); it != S.rend(); it++) {
        if(!VT[*it]) {
            cnt++;
            dfs1(*it);
        }
    }
}
void afisare() {
    cout << cnt << '\n';
    for(int i = 1; i <= cnt; i++) {
        for(auto j : conexe[i]) {
            g << j << ' ';
        }
        g << '\n';
    }
}
int main() {
    citire();
    kosaraju();
    afisare();
}