Cod sursa(job #3285985)

Utilizator nusuntvictorVictor Stefan nusuntvictor Data 13 martie 2025 17:23:44
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define mod 1000000007
#define NMAX 100001
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector<vector<int>>graf(NMAX);
vector<int>ids(NMAX),low(NMAX);
bitset<NMAX>onstack,vis;
stack<int>st;
int id,scc_cnt;
vector<int>ans[100005];
void dfs(int node){
    st.push(node);
    onstack[node]=true;
    ids[node]=low[node]=++id;
    vis[node]=1;
    for(const auto & neighbour : graf[node]){
        if(vis[neighbour]==0)
            dfs(neighbour);
        if(onstack[neighbour])
            low[node]=min(low[node],low[neighbour]);
    }

    if(ids[node]==low[node]){
        while(!st.empty()){
            int k=st.top();
            st.pop();
            onstack[k]=false;
            low[k]=ids[node];
            ans[scc_cnt].push_back(k);
            if(k==node)
                break;
        }
            scc_cnt++;
    }


}

vector<int>find_SCC(int n){
    for(int i=1; i<=n; ++i)
        if(vis[i]==0)
            dfs(i);
    return low;
}

int main()
{

    int n,m;
    f>>n>>m;
    for(int i=1; i<=m; ++i){
        int x,y;
        f>>x>>y;
        graf[x].push_back(y);
    }

    find_SCC(n);
    g<<scc_cnt<<'\n';
    for(int i=0; i<scc_cnt; ++i,g<<'\n')
        for(const auto & j : ans[i])
            g<<j<<' ';

    return 0;

}