Cod sursa(job #2974433)

Utilizator andu2006Alexandru Gheorghies andu2006 Data 4 februarie 2023 09:26:59
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
/*int Time(){
    return chrono::steady_clock::now().time_since_epoch().count();
}
random_device rd;
mt19937_64 gen(rd());
int uniform_rand(int l, int r){
    uniform_int_distribution<ll> rnd(l,r);
    return rnd(gen);
}*/
const int NMAX=1e5+5;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
stack<ll> s;
vector<ll> edg[NMAX];
vector<vector<ll>> components;
ll low[NMAX],tin[NMAX],id;
bool visited[NMAX];
void dfs(ll u){
    visited[u]=1,tin[u]=low[u]=++id;
    s.push(u);
    for(auto it : edg[u]){
        if(tin[it]==0){
            dfs(it);
            low[u]=min(low[u],low[it]);
        }
        else if(visited[it]){
            low[u]=min(low[u],tin[it]);
        }
    }
    if(low[u]==tin[u]){
        components.emplace_back();
        while(!s.empty()){
            ll x=s.top();
            s.pop();
            visited[x]=0;
            components.back().push_back(x);
            if(x==u) break;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    ll n,m;
    fin>>n>>m;
    for(ll i=0;i<m;i++){
        ll u,v; fin>>u>>v;
        edg[u].push_back(v);
    }
    for(ll i=1;i<=n;i++)
        if(tin[i]==0)
            dfs(i);
    fout<<components.size()<<'\n';
    for(auto it : components){
        //fout<<it.size()<<' ';
        for(auto it2: it)
            fout<<it2<<' ';
        fout<<'\n';
    }
    return 0;
}