Cod sursa(job #2929512)

Utilizator pinmelissa05Pintenaru-Dumitrescu Nicole Melissa pinmelissa05 Data 25 octombrie 2022 23:35:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

void creategraph(int m, vector<int> lista_g[], vector<int> lista_gt[]) { //creeam graful si graful transpus
    int x, y;
    for (int i = 0; i <= m - 1; i++) {
        in >> x >> y;
        lista_g[x].push_back(y);
        lista_gt[y].push_back(x);
    }
}

void DFS_G(int start, int viz[], vector<int> lista_g[], stack<int> &stiva) {
    viz[start] = 1;
    for (auto it = lista_g[start].begin(); it!=lista_g[start].end(); it++) {
        int y = *it;
        if (viz[y] == 0)
            DFS_G(y, viz, lista_g, stiva);
    }
    stiva.push(start);
}

void DFS_Gt(int start, int viz[], vector<int> lista_gt[], vector<int> &parcurgere) {
    viz[start] = 1;
    parcurgere.push_back(start);
    for (auto it = lista_gt[start].begin(); it!=lista_gt[start].end(); it++) {
        int y = *it;
        if (viz[y] == 0)
            DFS_Gt(y, viz, lista_gt, parcurgere);
    }
}

int main() {
    int m, n;
    vector<int> lista_g[100001], lista_gt[100001];

    in >> n >> m;
    creategraph(m, lista_g, lista_gt);

    stack<int> stiva;
    int viz[100001] = {0};
    for (int i = 1; i <= n; i++)
        if (viz[i] == 0)
            DFS_G(i, viz, lista_g, stiva);

    for (int i = 1; i <= n; i++)
        viz[i] = 0;

    int nr_cc = 0;//nr comp conexe
    vector<vector<int>> comp_c;//comp conexe
    while (!stiva.empty()) {
        int x = stiva.top();
        stiva.pop();
        if (viz[x] == 0) {
            nr_cc++;

            vector<int> parcurgere;
            DFS_Gt(x, viz, lista_gt, parcurgere);

            comp_c.push_back(parcurgere);
        }
    }

    out << nr_cc << endl;
    for (int i = 0; i < nr_cc; i++) {
        for(auto it = comp_c[i].begin(); it !=comp_c[i].end(); it++)
            out << *it << ' ';
        out << endl;
    }

    return 0;
}