Cod sursa(job #2665215)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 30 octombrie 2020 13:28:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include<stdio.h>
#include<vector>

using namespace std;

#define NMAX 200005

vector<int> ctc[NMAX];
int num_ctc, n, m;
int ctc_of[NMAX], viz[NMAX];
vector<int> graph[NMAX], graph_t[NMAX], ordered_list;

void dfs1(int node) {
    if(viz[node])
        return ;
        
    viz[node] = 1;
    for(auto vecin : graph[node]) {
        dfs1(vecin);
    }
    ordered_list.push_back(node);
}

void dfs2(int node, int index_ctc) {
    if(ctc_of[node])
        return ;
    
    ctc_of[node] = index_ctc;
 //   printf("%d %d\n", node, index_ctc);
    ctc[index_ctc].push_back(node);
    
    for(auto vecin : graph_t[node]) {
        dfs2(vecin, index_ctc);
    }
}

int main() {
    int a, b;
    
	freopen("ctc.in","r",stdin);
freopen("ctc.out", "w",stdout);

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &a, &b);
        graph[a].push_back(b);
        graph_t[b].push_back(a);
    }
    
    for(int i = 1; i <= n; i++) {
        if(!viz[i]) {
            dfs1(i);
        }
    }
    
    for(int i = n - 1; i >= 0; i--) {
        if(!ctc_of[ordered_list[i]]) {
            dfs2(ordered_list[i], ++num_ctc);
        }
    }
    
    printf("%d\n", num_ctc);
    for(int i = 1; i <= num_ctc; i++) {
        for(auto node : ctc[i]) {
            printf("%d ", node);
        }
        printf("\n");
    }
    
    return 0;
}