Cod sursa(job #2698551)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 22 ianuarie 2021 14:24:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std; 

const int Nmax = 100005;

vector <int> G[Nmax];
int lvl[Nmax];
int low[Nmax];
stack < pair <int, int> > stk;
vector < vector <int> > comp;

void get_comp(pair <int, int> edge) {
    vector <int> temp_comp;

    while (true) {
        pair <int, int> tp = stk.top();
        stk.pop();
        temp_comp.push_back(tp.first);
        temp_comp.push_back(tp.second);

        if (tp == edge)
            break;
    }

    sort(temp_comp.begin(), temp_comp.end());
    temp_comp.erase(unique(temp_comp.begin(), temp_comp.end()), temp_comp.end());

    comp.push_back(temp_comp);

    temp_comp.clear();
}

void DFS(int node = 1, int parent = 0) {
    low[node] = lvl[node] = lvl[parent] + 1;

    for (int it : G[node]) {
        if (it == parent) 
            continue;
    
        if (!lvl[it]) {
            stk.push({node, it});
            DFS(it, node);

            low[node] = min(low[node], low[it]);
            if (low[it] >= lvl[node]) 
                get_comp({node, it});
        }
        else 
            low[node] = min(low[node], lvl[it]);
    }
}

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

    int n, m;
    cin >> n >> m;

    while (m--) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    DFS();

    cout << comp.size() << '\n';
    for (auto& c : comp) { 
        for (int it : c)
            cout << it << ' ';
        cout << '\n';
    }

    return 0;
}