Cod sursa(job #3371814)

Utilizator ursus161Stefan Ghetu ursus161 Data 31 octombrie 2026 21:33:18
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>

std::vector<std::vector<int>> graf, grafT;
std::vector<int> comp;              // comp[i] = componenta lui i, 0 = încă neatribuit
std::vector<bool> plus, minus;


// unde pot ajunge din nod
void dfsPlus(int nod) {
    plus[nod] = true;
    for (int v : graf[nod])
        if (!plus[v] && comp[v] == 0)
            dfsPlus(v);
}

// cine poate ajunge în nod (DFS pe transpus)
void dfsMinus(int nod) {
    minus[nod] = true;
    for (int v : grafT[nod])
        if (!minus[v] && comp[v] == 0)
            dfsMinus(v);
}

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

    int n, m;
    fin >> n >> m;
    graf.resize(n + 1);
    grafT.resize(n + 1);
    comp.resize(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        graf[x].push_back(y);
        grafT[y].push_back(x);   // săgeata întoarsă
    }

    int nr = 0;
    for (int x = 1; x <= n; x++) {
        if (comp[x] != 0) continue;   // x e deja într-o componenta

        nr++;
        plus.assign(n + 1, false);
        minus.assign(n + 1, false);

        dfsPlus(x);
        dfsMinus(x);

        for (int i = 1; i <= n; i++)
            if (plus[i] && minus[i])
                comp[i] = nr;
    }

    fout << nr << "\n";
    for (int c = 1; c <= nr; c++) {
        for (int i = 1; i <= n; i++)
            if (comp[i] == c) fout << i << " ";
        fout << "\n";
    }
}