Cod sursa(job #1999227)

Utilizator MaligMamaliga cu smantana Malig Data 10 iulie 2017 17:35:28
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 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];

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

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

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

    for (int i=1;i <= N;++i) {
        if (inComp[i]) {
            continue;
        }

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