Cod sursa(job #3315044)

Utilizator Tudor.1234Holota Tudor Matei Tudor.1234 Data 11 octombrie 2025 22:57:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include "bits/stdc++.h"
#define int long long
#define vi std :: vector < int >
#define vivi std :: vector < vi >
#define pb push_back

const int NMAX = 1e5;

int n, m, nr_comp;
vi G_first[NMAX + 5], G_second[NMAX + 5], order, componente[NMAX + 5];
bool vis[NMAX + 5];

void DFS_Delete_Mark(int node){
    vis[node] = false;
    for(auto i : G_second[node]){
        if(vis[i]){
            DFS_Delete_Mark(i);
        }
    }
    componente[nr_comp].pb(node);
}

void DFS_Driver_delete_mark(){
    for(int i = n - 1; i >= 0; i--){
        if(vis[order[i]]){
            nr_comp++;
            DFS_Delete_Mark(order[i]);
        }
    }
}

void DFS_Mark(int node){
    vis[node] = true;
    for(auto i : G_first[node]){
        if(!vis[i]){
            DFS_Mark(i);
        }
    }
    order.pb(node);
}

void DFS_Driver_mark(){
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            DFS_Mark(i);
        }
    }
}

void Print(){
    std :: cout << nr_comp << '\n';
    for(int i = 1; i <= nr_comp; i++){
        for(auto j : componente[i]){
            std :: cout << j << ' ';
        }
        std :: cout << '\n';
    }
}

void Read(){
    std :: cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        std :: cin >> x >> y;
        G_first[x].pb(y);
        G_second[y].pb(x);
    }
}

signed main(){
    std :: ios_base :: sync_with_stdio(false);
    std :: cin.tie(nullptr);

    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    Read();
    DFS_Driver_mark();
    DFS_Driver_delete_mark();
    Print();

    return 0;
}