Cod sursa(job #2351963)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 22 februarie 2019 20:54:33
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <stack>
#include <cassert>

using namespace std;

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

stack<pair<int, int>> stk;
vector<vector<int>> ans;

void getcomponent(int x, int y) {
    vector<int> aux;
    int a = 0, b = 0;

    do {
        a = stk.top().first;
        b = stk.top().second;
        aux.push_back(a);
        aux.push_back(b);
        stk.pop();
    } while(a != x || b != y);

    ans.push_back(aux);
}

void dfs(int node, int dad, int x, const vector<vector<int>> &g, vector<int> &dp, vector<int> &h) {
    dp[node] = h[node] = x;

    for(auto it : g[node]) {
        if(it == dad)
            continue;
        if(!h[it]) {
            stk.push({node, it});
            dfs(it, node, x + 1, g, dp, h);

            dp[node] = min(dp[node], dp[it]);
            if(h[node] <= dp[it])
                getcomponent(node, it);

        } else
            dp[node] = min(dp[node], h[it]);
    }
}

int main() {

    int n, m;
    in >> n >> m;
    vector<vector<int>> g(n + 1);
    for(int i = 1; i <= m; i ++) {
        int a, b;
        in >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<int> dp(n + 1, 0);
    vector<int> h(n + 1, 0);
    dfs(1, 0, 1, g, dp, h);

    out << ans.size() << "\n";
    for(auto &it : ans) {
        sort(it.begin(), it.end());
        int last = -1;
        for(auto it2 : it) {
            if(it2 != last)
                out << it2 << " ";
            last = it2;
        }

        out << "\n";
    }

    return 0;
}