Cod sursa(job #3325775)

Utilizator Sebi_RipaSebastian Ripa Sebi_Ripa Data 26 noiembrie 2025 14:31:27
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
#include <stack>
#include <set>

using namespace std;

ifstream cin ("biconex.in");
ofstream cout ("biconex.out");

vector <int> adj[100005];
int lvl[100005], low[100005], cnt = 1;
bool visited[100005];
stack <pair<int, int>> s;
set <int> cmp[100005];

void dfs(int node, int dad) {
    visited[node] = 1;
    low[node] = lvl[node] = lvl[dad] + 1;
    for(auto x : adj[node]) {
        if(x == dad)
            continue;
        if(visited[x]) {
            low[node] = min(low[node], low[x]);
            continue;
        }

        s.push({x, node});
        dfs(x, node);
        low[node] = min(low[node], low[x]);

        if(lvl[node] <= low[x]) {
            while(true) {
                int n1 = s.top().first, n2 = s.top().second;
                s.pop();
                cmp[cnt].insert(n1);
                cmp[cnt].insert(n2);
                if(x == n1 && node == n2)
                    break;
            }
            cnt++;
        }
    }
}

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

    dfs(1, 1);

    if(s.empty())
        cnt--;
    while(!s.empty()) {
        int n1 = s.top().first, n2 = s.top().second;
        s.pop();
        cmp[cnt].insert(n1);
        cmp[cnt].insert(n2);
    }

    cout << cnt << '\n';
    for(int i = 1; i <= cnt; i++) {
        for(auto x : cmp[i])
            cout << x << ' ';
        cout << '\n';
    }
}