Cod sursa(job #2878871)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 28 martie 2022 01:14:28
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;
const long long NR = 1e6 + 25;

vector<vector<int>> v;
vector<int> highest, vis, curr, nodes;
int n, m, lvl;
vector<vector<int>> scc;

void dfs(int nod) {
    vis[nod] = lvl;
    highest[nod] = lvl;
    ++lvl;
    nodes.push_back(nod);
    curr[nod] = 1;
    for (auto it : v[nod]) {
        if (!vis[it]) {
            dfs(it);
            highest[nod] = min(highest[nod], highest[it]);
        } else {
            if (curr[it]) {
                highest[nod] = min(highest[nod], highest[it]);
            }
        }
    }
    if (vis[nod] == highest[nod]) {
        vector<int> temp;
        int node = -1;
        while (node != nod) {
            node = nodes.back();
            curr[nodes.back()] = 0;
            temp.emplace_back(nodes.back());
            nodes.pop_back();
        }
        scc.emplace_back(temp);
    }
}

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

signed main() {
    int x, y;
    in >> n >> m;
    v.resize(n + 1, vector<int>());
    highest.resize(n + 1, 0);
    vis.resize(n + 1, 0);
    curr.resize(n + 1, 0);
    for (int i = 1; i <= m; ++i) {
        in >> x >> y;
        v[x].emplace_back(y);
    }
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    out << scc.size() << '\n';
    for (auto it : scc) {
        sort(it.begin(), it.end());
        for (auto it2 : it) {
            out << it2 << ' ';
        }
        out << '\n';
    }
    return 0;
}