Cod sursa(job #2668138)

Utilizator dianapingu1Diana Vasiliu dianapingu1 Data 4 noiembrie 2020 15:41:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 200005;

vector<int> graf[NMAX];
vector<int> graf_t[NMAX];
vector<int> ordered_list;
vector<int> comp[NMAX];

int comp_nod[NMAX];
int viz[NMAX];

int nrcomp;

void dfs1(int nod) {
    viz[nod] = 1;

    for (auto &vec : graf[nod]) {
        if (!viz[vec]) {
            dfs1(vec);
        }
    }
    ordered_list.push_back(nod);
}

void dfs2(int nod, int index) {
    comp_nod[nod] = index;
    comp[index].push_back(nod);

    for (auto &vec : graf_t[nod]) {
        if (!comp_nod[vec]) {
            dfs2(vec, index);
        }
    }
}

int main() {
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");

    int a,b,m,n;
    fin >> n >> m;
    for(int i = 0; i < m; i++) {
        fin >> a >> b;
        graf[a].push_back(b);
        graf_t[b].push_back(a);
    }

    for(int i = 1; i <= n; i++) {
        if (!viz[i]) {
            dfs1(i);
        }
    }

    for(int i = n - 1; i >= 0; i--) {
        if (!comp_nod[ordered_list[i]]) {
            dfs2(ordered_list[i], ++nrcomp);
        }
    }

    fout << nrcomp << "\n";
    for (int i = 1; i <= nrcomp; i++) {
        for (auto &nod : comp[i]) {
            fout << nod << " ";
        }
        fout << "\n";
    }


    fin.close();
    fout.close();
    return 0;
}