Cod sursa(job #1502430)

Utilizator stefanzzzStefan Popa stefanzzz Data 14 octombrie 2015 17:30:41
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#define MAXN 100005
using namespace std;

int n, m, x, y, nrCtc;
bool uz[MAXN];
vector<int> G[MAXN], GT[MAXN], ord;
vector<int> ctc[MAXN];

void DFSP(int u) {
    uz[u] = 1;
    for(auto x: G[u])
        if(!uz[x])
            DFSP(x);
    ord.push_back(u);
}

void makeCtc(int u, int &ctcId) {
    uz[u] = 1;
    ctc[ctcId].push_back(u);
    for(auto x: GT[u])
        if(!uz[x])
            makeCtc(x, ctcId);
}

int main()
{
    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", &x, &y);
        G[x].push_back(y);
        GT[y].push_back(x);
    }

    for(int i = 1; i <= n; i++)
        if(!uz[i])
            DFSP(i);

    memset(uz, 0, sizeof(uz));
    for(int i = ord.size() - 1; i > 0; i--)
        if(!uz[ord[i]])
            makeCtc(ord[i], ++nrCtc);

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

    return 0;
}