Cod sursa(job #1999307)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 10 iulie 2017 21:09:30
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.41 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");

#define ll long long
#define pb push_back
const int inf = 1e9 + 5;
const int NMax = 4e3 + 5;

int N,M,nrComp;
bool drum[NMax][NMax],inComp[NMax];
vector<int> v[NMax],comp[NMax];
// drum[i][j] - reprezinta initial daca exista arcul (i,j),
//              ulterior inseamna ca exista drum de la i la j;
// inComp[i] = true daca s-a gasit deja componenta lui i;
// nrComp = numarul de componente gasite pana la momentul de fata;
// v[i] - lista de adiacenta a nodului i;
// comp[i] - nodurile ce fac parte din a i-a componenta tare conexa gasita;

int main() {
    in>>N>>M;
    while (M--) {
        int x,y;
        in>>x>>y;

        drum[x][y] = true;
    }

    for (int i=1; i <= N;++i) {
        drum[i][i] = true;
    }

    // se utilizeaza algoritmul Floyd - Roy - Warshall
    // pentru a gasi daca exista drumuri intre oricare doua noduri
    for (int k=1;k <= N;++k) {
        for (int i=1;i <= N;++i) {
            for (int j=1;j <= N;++j) {
                if (drum[i][k] && drum[k][j]) {
                    drum[i][j] = true;
                }
            }
        }
    }

    // doua noduri vor putea face parte din aceeasi componenta tare conexa
    // doar daca exista drum de la i la j si drum de la j la i
    for (int i=1;i <= N;++i) {
        for (int j=1;j <= N;++j) {
            if (drum[i][j] && drum[j][i]) {
                continue;
            }
            drum[i][j] = 0;
            drum[j][i] = 0;
        }
    }

    // daca exista drumurile (i,j) si (j,k) vor exista si drumurile (i,k),(k,i)
    // deci se poate arata usor ca daca n noduri
    // sunt in aceeasi componenta tare conexa
    // atunci fiecare nod va avea drum catre toate celelalte
    for (int i=1;i <= N;++i) {
        if (inComp[i]) {
            continue;
        }

        // cautam nodurile spre care nodul i are drum si inapoi
        ++nrComp;
        for (int j=1;j <= N;++j) {
            if (drum[i][j]) {
                comp[nrComp].pb(j);
                inComp[j] = true;
            }
        }
    }

    out<<nrComp<<'\n';

    for (int k=1;k <= nrComp;++k) {
        for (auto node : comp[k]) {
            out<<node<<' ';
        }
        out<<'\n';
    }

    in.close();
    out.close();
    return 0;
}