Cod sursa(job #3373181)

Utilizator mar_parapeanumaria parapeanu mar_parapeanu Data 6 noiembrie 2026 11:47:21
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <vector>

std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");

void dfs(int nod, std::vector<std::vector<int>> &g, std::vector<int> &visited, const std::vector<bool> &esteComp) {
    if (visited[nod] != 1 && esteComp[nod] == false) {
        visited[nod] = 1;
        for (auto vecin : g[nod]) {
            if (visited[vecin] != 1)
                dfs(vecin, g, visited, esteComp);
        }
    }
}

void comp(std::vector<int> &plus, std::vector<int> &minus, std::vector<std::vector<int>> &c, int cnt, int n, std::vector<bool> &esteComp) {
    for (int i = 1; i<=n; i++) {
        if (plus[i] == 1 && minus[i] == 1) {
            c[cnt].push_back(i);
            esteComp[i] = true;
        }
    }
}

int main() {
    int n, m, x, y, cnt = 0;
    fin >> n >> m;
    std::vector<std::vector<int>> graph(n+1), graphT(n+1);
    std::vector<int> visitedPlus (n+1, 0), visitedMinus(n+1, 0);
    std::vector<std::vector<int>> componente(n+1);
    std::vector<bool> esteComp(n+1, false);
    while (fin >> x >> y) {
        graph[x].push_back(y);
        graphT[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        if (esteComp[i] == false) {
            visitedMinus.assign(n+1, 0), visitedPlus.assign(n+1, 0);
            cnt ++;
            dfs(i, graph, visitedPlus, esteComp);
            dfs(i, graphT, visitedMinus, esteComp);
            comp(visitedPlus, visitedMinus, componente, cnt, n, esteComp);
        }
    }
    fout << cnt<< "\n";
    for (int i = 1; i<=cnt; i++) {
        for (auto nod : componente[i])
            fout << nod << " ";
        fout << "\n";
    }
}