Cod sursa(job #2147715)

Utilizator mariakKapros Maria mariak Data 28 februarie 2018 22:17:00
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 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){
        scc[count_scc].push_back(st.back());
        st.pop_back();
    }
    scc[count_scc].push_back(node);
    st.pop_back();
    count_scc ++;
}

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

    for(int son : G[node]){
        if(!seen.test(son)){
            dfs(son);
            low[node] = min(low[node], low[son]);
        }
        else low[node] = min(low[node], disc[son]);
    }
    if(low[node] == disc[node])
        SCC(node);
}

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);
    }
    dfs(1);
    Write();
    return 0;
}