Cod sursa(job #2148024)

Utilizator mariakKapros Maria mariak Data 1 martie 2018 14:30:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <bits/stdc++.h>
FILE *fin  = freopen("ctc.in", "r", stdin);
FILE *fout = freopen("ctc.out", "w", stdout);

using namespace std;
const int MAX = 1e5 + 2;
int n, m, t, count_scc;
vector <int> G[MAX];
bitset <MAX> seen;
vector <int> scc[MAX];
vector <int> st;
int low[MAX], disc[MAX];

void SCC(int node){
    while(!st.empty() && st.back() != node){
        int x = st.back();
        seen.reset(x);
        scc[count_scc].push_back(x);
        st.pop_back();
    }
    scc[count_scc].push_back(node);
    st.pop_back();
    seen.reset(node);
}

void dfs(int node){
    st.push_back(node);
    low[node] = disc[node] = ++ t;
    seen.set(node);

    for(int son : G[node]){
        if(!disc[son]){
            dfs(son);
            low[node] = min(low[node], low[son]);
        } /// tree edge
        else if(seen.test(son))
            low[node] = min(low[node], disc[son]); /// back edge
        /// else we encounter a cross edge which should be avoid
    }
    if(low[node] == disc[node]){
        SCC(node);
        count_scc ++;
    }
}

void Write(){
    printf("%d\n", count_scc);
    for(int i = 0; i < count_scc; ++ i){
        for(int node : scc[i])
            printf("%d ", node);
        printf("\n");
    }
}
int main(){
    int u, v;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++ i){
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    for(int i = 1; i <= n; ++ i)
        if(!disc[i])
            dfs(i);
    Write();
    return 0;
}