Cod sursa(job #3123298)

Utilizator adaxndDobrica Nicoleta Adriana adaxnd Data 22 aprilie 2023 23:40:01
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>

using namespace std;

#define NMAX 100001

struct Edge {
    int u, v;
};

vector<int> dis(NMAX, -1);
vector<int> low(NMAX, -1);
vector<bool> vis(NMAX, false);
stack<Edge> st;

vector<set<int> > ans;

void biconex(int node, int parent, int time, vector<int> adj[NMAX]) {
    dis[node] = low[node] = ++time;
    vis[node] = true;

    for (auto neigh : adj[node]) {
        if (neigh == parent) {
            continue;
        }

        if (vis[neigh]) {
            low[node] = min(low[node], dis[neigh]);
        } else {
            Edge e;
            e.u = node;
            e.v = neigh;
            st.push(e);

            biconex(neigh, node, time, adj);
            low[node] = min(low[node], low[neigh]);

            if (low[neigh] >= dis[node]) {
                int u = 0, v = 0;
                set<int> p;

                do {
                    u = st.top().u;
                    v = st.top().v;
                    p.insert(u);
                    p.insert(v);

                    st.pop();
                } while (u != node && v != neigh);

                ans.push_back(p);
            }
        }
    }
}

void print() {
    ofstream fout("biconex.out");
    
    fout << ans.size() << "\n";

    for (auto p : ans) {
        for (auto x : p) {
            fout << x << " ";
        }
        fout << "\n";
    }

}

int main() {
    ifstream fin("biconex.in");

    int n, m;

    fin >> n >> m;

    vector<int> adj[n + 1];

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

    biconex(1, -1, 0, adj);
    print();

    return 0;
}