Cod sursa(job #2157883)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 9 martie 2018 23:22:36
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 2.55 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];
bool viz[100100];

vector < int > V[100100];
stack < PII > St;
queue < set < int > > Q;

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){
                set < int > Ans;
                while (St.top() != make_pair(node, it)){
                    PII E = St.top();
                    Ans.insert(E.x);
                    Ans.insert(E.y);
                    St.pop();
                }
                PII E = St.top();
                Ans.insert(E.x);
                Ans.insert(E.y);
                Q.push(Ans);
                St.pop();
            }

            else if (Low[it] >= Depth[node]){
                set < int > Ans;
                while (St.top() != make_pair(node, it)){
                    PII E = St.top();
                    Ans.insert(E.x);
                    Ans.insert(E.y);
                    St.pop();
                }
                PII E = St.top();
                Ans.insert(E.x);
                Ans.insert(E.y);
                Q.push(Ans);
                St.pop();
            }

        } else if (it != dad && Low[node] > Depth[it]){
            Low[node] = Depth[it];
            St.push({node, 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);
        set < int > Ans;
        while (St.size()){
            PII E = St.top();
            Ans.insert(E.x);
            Ans.insert(E.y);
            St.pop();
        }
        if (Ans.size()) Q.push(Ans);
    }

    cout << Q.size() << "\n";
    while (Q.size()){
        set < int > Ans = Q.front();
        for (auto it: Ans) cout << it << " ";
        Q.pop();
        cout << "\n";
    }


    return 0;
}