Cod sursa(job #1561960)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 4 ianuarie 2016 18:16:09
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

#define DIM 5005

int N, M, Tabel[DIM][DIM], viz[DIM], p;
vector <vector <int> > Graph;

void Citire();
void RW();
void Solve();
void comp_tare(int nod);
void Afisare();

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

    Citire();
    RW();
    Solve();
    Afisare();

    return 0;
}

void Citire() {
    int x, y;

    scanf("%d %d\n", &N, &M);

    Graph.resize(N + 1);

    for(int i = 1; i <= M; ++i) {
        scanf("%d %d\n", &x, &y);

        Tabel[x][y] = 1;
        Graph[x].push_back(y);
    }
}

void RW() {
    for(int k = 1; k <= N; ++k) {
        for(int i = 1; i <= N; ++i) {
            for(int j = 1; j <= N; ++j) {
                if(Tabel[i][j] == 0 && Tabel[i][k] && Tabel[k][j]) {
                    Tabel[i][j] = 1;
                }
            }
        }
    }
}

void Solve() {
    for(int i = 1; i <= N; ++i) {
        if(viz[i] == 0) {
            ++p;
            comp_tare(i);
        }
    }
}

void comp_tare(int nod) {
    viz[nod] = p;

    for(auto x: Graph[nod]) {
        if(viz[x] == 0 && Tabel[nod][x] == 1 && Tabel[x][nod] == 1) {
            comp_tare(x);
        }
    }
}

void Afisare() {
    cout << p << '\n';

    for(int i = 1; i <= p; ++i) {
        for(int j = 1; j <= N; ++j) {
            if(viz[j] == i) {
                cout << j << ' ';
            }
        }

        cout << '\n';
    }
}