Cod sursa(job #3311444)

Utilizator paulihno15Ciumandru Paul paulihno15 Data 22 septembrie 2025 14:09:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>
#define NMAX 100000

using namespace std;

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

int n, m, x, y, tmp;
int niv[NMAX + 2], low[NMAX + 2];
vector<int> gr[NMAX + 2];
bool in_stv[NMAX + 2];
stack<int> st;
vector<vector<int>> ctc;

void dfs(int nod) {
    niv[nod] = low[nod] = ++tmp;
    in_stv[nod] = 1;
    st.push(nod);

    for (int vec : gr[nod]) {
        if (!niv[vec]) {
            dfs(vec);
            low[nod] = min(low[nod], low[vec]);
        }
        else if (in_stv[vec]) {
            low[nod] = min(low[nod], niv[vec]);
        }
    }

    if (low[nod] == niv[nod]) {
        vector<int> comp;

        int nd;
        do {
            nd = st.top();
            st.pop();
            in_stv[nd] = 0;
            comp.emplace_back(nd);
        } while (nd != nod);

        ctc.emplace_back(comp);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> n >> m;

    while (m--) {
        fin >> x >> y;
        gr[x].emplace_back(y);
    }

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

    fout << ctc.size() << '\n';
    for (int i = 0; i < ctc.size(); i++) {
        for (auto it : ctc[i]) {
            fout << it << ' ';
        }
        fout << '\n';
    }
    return 0;
}