Cod sursa(job #1921537)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 10 martie 2017 13:05:35
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;

int nxt;
int disc[100005], low[100005];
stack < pair<int, int> > s;
bool viz[100005];
vector < vector <int> > cmp;
vector <int> ax;
vector <int> adj[100005];

void dfs(int node, int parent){
    ++nxt;
    disc[node] = low[node] = nxt;
    s.push({parent, node});
    viz[node] = 1;
    for(auto it : adj[node]){
        if(viz[it] == 0){
            dfs(it, node);
            low[node] = min(low[node], low[it]);
            if(low[it] >= disc[node] || (parent == 0 && adj[node].size() > 1)){
                int x, y;
                ax.clear();
                do{
                    x = s.top().first;
                    y = s.top().second;
                    ax.push_back(x);
                    ax.push_back(y);
                    s.pop();
                }while(x != node || y != it);
                cmp.push_back(ax);
            }
        }else if(it != parent){
            low[node] = min(low[node], disc[it]);
        }
    }
}

int main(){
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    int n,m,i,x,y;
    fin>>n>>m;
    for(i = 1;i <= m;i++){
        fin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1, 0);
    fout<<cmp.size()<<'\n';;
    for(auto &v : cmp){
        sort(v.begin(), v.end());
        auto it = unique(v.begin(), v.end());
        v.resize(it - v.begin());
        for(auto it : v){
            fout<<it<<' ';
        }
        fout<<'\n';
    }
    return 0;
}