Cod sursa(job #3152518)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 25 septembrie 2023 15:56:29
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n, low[100005], found[100005];
vector<int> adj[100005];
int m, x, y, t, k, c;
int st[100005];
vector<int> comp[100005];
void dfs(int nod) {
    found[nod] = t;
    low[nod] = t;
    t++;
    st[++k] = nod;

    for (auto it : adj[nod]) {
        if (found[it] == 0) {
            dfs(it);
            if (low[it] >= found[nod]) {
                c++;
                while (st[k] != nod) {
                    comp[c].push_back(st[k]);
                    k--;
                }
                comp[c].push_back(nod);
            }

            low[nod] = min(low[it], low[nod]);
        } else {
            low[nod] = min(low[nod], found[it]);
        }
    }
}

int main()
{
    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        in >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) {
        if (found[i] == 0) {
            t = 1;
            k = 0;
            dfs(i);
        }
    }

    out << c << '\n';
    for (int i = 1; i <= c; i++) {
        for (auto it : comp[i]) {
            out << it << " ";
        }
        out << '\n';
    }
    return 0;
}