Cod sursa(job #3296219)

Utilizator iordacheMatei Iordache iordache Data 12 mai 2025 10:19:29
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=1e5+5;
vector<int> g[N],rg[N];
vector<int> ord;
bool vis[N];
vector<vector<int>> comp;
vector<int> cc;
void dfs(int node)
{
    vis[node]=1;
    cc.pb(node);
    for(auto x:g[node])
    {
        if(vis[x]) continue;
        dfs(x);
    }
    ord.pb(node);
}
void dfs2(int node)
{
    vis[node]=1;
    cc.pb(node);
    for(auto x:rg[node])
    {
        if(vis[x]) continue;
        dfs2(x);
    }
}
signed main()
{
    ifstream cin("ctc.in");ofstream cout("ctc.out");
    int n,m;
    cin>>n>>m;
    for(int _=1;_<=m;++_)
    {
        int u,v;cin>>u>>v;
        g[u].pb(v);rg[v].pb(u);
    }
    for(int i=1;i<=n;++i)
    {
        if(vis[i]) continue;
        dfs(i);
    }
    for(int i=1;i<=n;++i) vis[i]=0;
    reverse(ord.begin(),ord.end());
    for(auto x:ord)
    {
        if(vis[x]) continue;
        cc.clear();
        dfs2(x);
        comp.pb(cc);
    }
    cout<<comp.size()<<'\n';
    for(auto x:comp)
    {
        for(auto y:x) cout<<y<<" ";
        cout<<'\n';
    }
}