Cod sursa(job #3197036)

Utilizator adrian_zahariaZaharia Adrian adrian_zaharia Data 25 ianuarie 2024 15:34:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
#define FastIo() ios_base::sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
using namespace  std;
const int nmax = 100005;

vector<int> adj[nmax], adj_rev[nmax],ctc[nmax];
bitset<nmax> used;
vector<int> post_order;
int n,m,x,y,nr_ctc;

void dfs1(int x){
    used[x]=true;
    for(int y:adj[x])
        if(!used[y])
            dfs1(y);
    post_order.push_back(x);
}
void dfs2(int x){
    used[x]=true;
    ctc[nr_ctc].push_back(x);
    for(int y: adj_rev[x])
        if(!used[y])
            dfs2(y);
}
int main(){
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    FastIo();
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        adj[x].push_back(y);
        adj_rev[y].push_back(x);
    }
    used.reset();
    for(int i=1;i<=n;i++) if(!used[i]) dfs1(i);

    used.reset();
    for(int i=n-1;i>=0;--i){
        x = post_order[i];
        if(!used[x]){
            nr_ctc++;
            dfs2(x);
        }
    }
    cout<<nr_ctc<<'\n';
    for(int ind=1;ind<=nr_ctc;ind++){
        int len = ctc[ind].size();
        for(int i=0;i<len;i++)
            cout<<ctc[ind][i]<<' ';
        cout<<'\n';
    }

    return 0;
}