Cod sursa(job #3030869)

Utilizator mihaicrisanMihai Crisan mihaicrisan Data 17 martie 2023 22:31:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e5 + 5;

int n, m, cnt , a, b;
vector<vector<int>> g(NMAX), gt(NMAX);
vector<bool> viz(NMAX);
stack<int> st;
vector<set<int>> ans(NMAX);

void dfsu(int node, int cnt) {
    viz[node] = true;

    ans[cnt].insert(node);

    for (int i : gt[node])
        if (!viz[i])
            dfsu(i, cnt);
}

void dfs(int node) {
    viz[node] = true;

    for (int i : g[node])
        if (!viz[i])
            dfs(i);

    st.push(node);
}

void kosaraju() {
    for (int i = 1; i <= n; i++)
        viz[i] = false;

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

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

    while (!st.empty()) {
        int curr = st.top();
        st.pop();

        if (!viz[curr]) {
            cnt++;
            dfsu(curr, cnt);
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> a >> b;
        g[a].push_back(b);
        gt[b].push_back(a);
    }

    kosaraju();

    fout << cnt << '\n';
    for (int i = 1; i <= cnt; i++) {
        for (auto it = ans[i].begin(); it != ans[i].end(); it++)
            fout << *it << ' ';
        fout << '\n';
    }
    return 0;
}