Cod sursa(job #2372589)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 7 martie 2019 10:05:26
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <iomanip>
#define ll long long
#define lsb(x) (x & -x)

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;
        stk.pop();
        aux.push_back(a);
        aux.push_back(b);
    } while(x != a && y != b);

    ans.push_back(aux);
}

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

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

            dp[node] = min(dp[node], dp[it]);

            if(dp[it] >= h[node]) {
                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<bool> visited(n + 1, 0);
    vector<int> dp(n + 1, 0);
    vector<int> h(n + 1, 0);
    h[1] = 1;
    dfs(1, 0, visited, dp, h, g);

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

    return 0;
}