Cod sursa(job #2046249)

Utilizator LucaSeriSeritan Luca LucaSeri Data 23 octombrie 2017 17:10:24
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;
const int maxn = 100010;
vector<int> gr[maxn];
int level[maxn], minim[maxn];
stack< pair<int, int> > muchii;
vector<int> componente[maxn];

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

int cnt = 0;
void biconex(int x, int y){
    int a, b;
    while(true){
        a = muchii.top().first;
        b = muchii.top().second;
        muchii.pop();
        componente[cnt].push_back(a);
        componente[cnt].push_back(b);
        if(a == x && b == y){
            return;
        }
    }
}

void dfs(int node, int boss, int nivel){
    level[node] = minim[node] = nivel;
    for(auto x : gr[node]){
        if(x == boss) continue;
        if(level[x] == 0){
            muchii.push({node, x});
            dfs(x, node, nivel+1);
            if(minim[x] >= level[node]){
                ++cnt;
                biconex(node, x);
            }

            minim[node] = min(minim[node], minim[x]);
        }
        else minim[node] = min(minim[node], level[x]);
    }

    return;
}
int main(){
    int n, m;
    f >> n >> m;
    for(int i = 0; i < m; ++i){
        int a, b;
        f >> a >> b;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }

    dfs(1, 0, 1);
    g << cnt << '\n';
    for(int i = 1; i <= cnt; ++i){
        sort(componente[i].begin(), componente[i].end());
        int used = 0;
        for(auto x : componente[i]){
            if(x == used) continue;
            used = x;
            g << x << ' ';
        }
        g << '\n';
    }
    return 0;
}