Cod sursa(job #2157908)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 9 martie 2018 23:48:15
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define MOD 1000000007

using namespace std;
typedef unsigned long long ll;
typedef pair< int , int > PII;
const int dirx[] = {-2, -1, 1, 2, 1, -1};
const int diry[] = {0, 1, 1, 0, -1, -1};
inline void debugMode()
{
#ifndef ONLINE_JUDGE
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
#endif
}

int n, m, Depth[100100], Low[100100], cnt;
bool viz[100100];

vector < int > V[100100], Ans[100100];
stack < PII > St;

void get_ans(int node, int it){
    cnt++;
    while (St.top() != make_pair(node, it)){
        PII E = St.top();
        Ans[cnt].pb(E.y);
        St.pop();
    }
    PII E = St.top();
    Ans[cnt].pb(E.x);
    Ans[cnt].pb(E.y);
    St.pop();
}

void dfs(int node, int dad, int depth){
    viz[node] = 1;
    Depth[node] = depth;
    Low[node] = depth;

    for (auto it: V[node]){
        if (!viz[it]){
            St.push({node, it});
            dfs(it, node, depth + 1);
            Low[node] = min(Low[node], Low[it]); 

            if (dad == -1 && V[node].size() > 1){
                get_ans(node, it);
            }
            else if (Low[it] >= Depth[node]){
                get_ans(node, it);
            }

        } else if (it != dad){
            Low[node] = min(Low[node], Depth[it]);
        }
    }
}

int main(){
    debugMode();
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;

    for (int i = 0, x, y; i < m; i++){
        cin >> x >> y;
        V[x].pb(y);
        V[y].pb(x);
    }

    for (int i = 1; i <= n; i++){
        if (viz[i]) continue;
        dfs(i, -1, 1);
    }

    cout << cnt << "\n";
    for (int i = 1; i <= cnt; i++){
        for (auto it: Ans[i]) cout << it << " ";
        cout << "\n";
    }

    return 0;
}