Cod sursa(job #1783601)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 19 octombrie 2016 10:10:56
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <vector>

using namespace std;

const int NMAX = 100010;

vector <int> G[NMAX];
vector <int> GT[NMAX];
vector <int> noduri;
vector <int> ctc[NMAX];

int N, M;
int viz[NMAX];
int comp[NMAX];

void dfs (int nod) {
    viz[nod] = 1;
    for (auto &it : G[nod]) {
        if ( !viz[it]) {
            dfs(it);
        }
    }
    noduri.push_back (nod);
}

void formComp (int nod, int rad) {
    if ( !comp[nod]) {
        comp[nod] = rad;
        ctc[rad].push_back(nod);
        for (auto &it : G[nod]) {
            formComp (it, rad);
        }
    }
}

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

    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);
    }

    dfs (1);

    for (auto &it : noduri) {
        formComp (it, it);
    }

    int radComp[NMAX], nrCtc = 0;
    for (int i = 1; i <= N; i++) {
        if (ctc[i].size() > 0) {
            nrCtc++;
            radComp[nrCtc] = i;
        }
    }

    for (int i = 1; i <= nrCtc; i++) {
        for (auto &it : ctc[i]) {
            printf ("%d ", it);
        }
        printf ("\n");
    }

    return 0;
}