Cod sursa(job #2192879)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 7 aprilie 2018 16:36:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<stdio.h>
#include<vector>
#define Nmax 100010
using namespace std;

int n, m , viz[Nmax], i , a , b , ctc, S[Nmax], nn, N, j;

vector<int> G[Nmax], T[Nmax], Ctc[Nmax];

void sortaret(int nod)  {
    int i, N = G[nod].size();
    viz[nod] = 1;

    for (i = 0; i < N; i++) {
        if (!viz[G[nod][i]]) sortaret(G[nod][i]);
    }
    
    S[--nn] = nod ; 
}

void dfs(int nod) {
    int i, N = T[nod].size(); 

    Ctc[ctc].push_back(nod);
    viz[nod] = 0;

    for (i = 0; i < N; i++) {
        if (viz[T[nod][i]]) dfs(T[nod][i]);
    }
}

int main() {
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    
    scanf("%d %d",&n,&m);

    for (i = 1; i <= m; i++) {
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
        T[b].push_back(a);
    }

    nn = n + 1 ;
    for (i = 1; i <= n; i++) {
        if(!viz[i]) sortaret(i);
    }

    for (i = 1; i <= n; i++) {
        if (viz[S[i]]) ctc++, dfs(S[i]);
    }

    printf("%d\n", ctc);
    for (i = 1; i <= ctc; i++) {
        N = Ctc[i].size();
        for (j = 0; j < N; j++) {
            printf("%d ", Ctc[i][j]);
        }
        printf("\n");
    }

    return 0 ;
}