Cod sursa(job #2157870)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 9 martie 2018 23:16:37
Problema Componente biconexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 2.46 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];
stack < PII > St;
set < int > Ans[1010];

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){
                cnt++;
                while (St.top() != make_pair(node, it)){
                    PII E = St.top();
                    Ans[cnt].insert(E.x);
                    Ans[cnt].insert(E.y);
                    St.pop();
                }
                PII E = St.top();
                Ans[cnt].insert(E.x);
                Ans[cnt].insert(E.y);
                St.pop();
            }

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

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


    return 0;
}