Cod sursa(job #1671241)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 1 aprilie 2016 15:05:55
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <numeric>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <fstream>
#include <cstdlib>
#include <map>
#include <stack>
#define pb push_back
#define mp make_pair
#define INF numeric_limits<int>::max()
#define lsb(x) (-x)&x
#define int64 long long
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector< vector<int> > adj,sol;
vector<int> lvl,low;
set<int> artV;
stack<int> st;
int n,m,bc;
void updateSol(int x,int y)
{
    bc++;
    while(st.top()!=y)
    {
        sol[bc].pb(st.top());
        st.pop();
    }
    sol[bc].pb(x);
    sol[bc].pb(y);
    st.pop();
}
void dfs(int x,int px,int level)
{
    lvl[x]=low[x]=level;
    int cnt=0;
    for(auto it: adj[x])
    if(it!=px)
    {
        if(lvl[it]==0)
        {
            st.push(it);
            dfs(it,x,level+1);
            cnt++;
            low[x]=min(low[x],low[it]);
            if(low[it]>=lvl[x] && px!=0)
            {
                artV.insert(x);
                updateSol(x,it);
            }
        }
        else
            low[x]=min(low[x],lvl[it]);
    }
    if(px==0 && cnt>=2)
        artV.insert(x);
}
int main()
{
    in>>n>>m;
    adj=sol=vector< vector<int> > (n+1);
    lvl=low=vector<int> (n+1);
    for(;m;m--)
    {
        int x,y;
        in>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    dfs(1,1,1);
    out<<bc<<'\n';
    for(int i=1;i<=bc;i++,out<<'\n')
    for(auto it: sol[i])
        out<<it<<' ';
    return 0;
}