Cod sursa(job #1966285)

Utilizator mariakKapros Maria mariak Data 15 aprilie 2017 08:24:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#define maxN 100002

FILE *fin  = freopen("ctc.in", "r", stdin);
FILE *fout = freopen("ctc.out", "w", stdout);

using namespace std;
int N, M;
vector <int> G[maxN];
vector <int> Gt[maxN];
vector <int> st;
int no_scc;
vector <int> scc[maxN];
bitset <maxN> used;


void dfs(int node){
    used.set(node);
    for(int son : G[node])
        if(!used.test(son))
            dfs(son);
    st.push_back(node);
}

void SCC(int node){
    used.set(node);
    scc[no_scc].push_back(node);
    for(int son : Gt[node])
        if(!used.test(son))
            SCC(son);
}

int main(){
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= M; ++ i){
        int x, y;
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    for(int i = 1; i <= N; ++ i)
        if(!used.test(i))
            dfs(i);
    used.reset();
    for(int i = 0; i < N; ++ i){
        int node = st[N - i - 1];
        if(!used.test(node)){
            SCC(node);
            no_scc ++;
        }
    }
    printf("%d\n", no_scc);
    for(int i = 0; i < no_scc; ++ i){
        for(int node : scc[i])
            printf("%d ", node);
        printf("\n");
    }
    return 0;
}