Cod sursa(job #1899066)

Utilizator GeanaVladGeana Vlad GeanaVlad Data 2 martie 2017 15:12:30
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <iostream>
#include<fstream>
#include<stack>
#include<queue>
#include<vector>
#define f first
#define s second
#define mp make_pair
#define pb push_back
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int>v[100010];
vector<int>ans[100010];
stack<pair<int,int> >st;
int timp,n,m,nr,comp[100010],a,b,lev[100010],low[100010],x,y,i,j,it,beg=1,tt[100010];
void add(int x,int y)
{
    nr++;
    comp[x]=comp[y]=nr;
    ans[nr].pb(x);
    ans[nr].pb(y);
    while(st.top().f!=x || st.top().s!=y)
    {
        a=st.top().f;
        b=st.top().s;
        st.pop();
        if(comp[a]!=nr)
        {
            ans[nr].pb(a);
            comp[a]=nr;
        }
        if(comp[b]!=nr)
        {
            ans[nr].pb(b);
            comp[b]=nr;
        }
    }
    st.pop();
}
void df(int x)
{
    lev[x]=low[x]=++timp;
    for(int k=0; k<v[x].size(); k++)
        if(v[x][k]!=tt[x])
        {
            if(!lev[v[x][k]])
            {
                st.push(mp(x,v[x][k]));
                tt[v[x][k]]=x;
                df(v[x][k]);
                low[x]=min(low[x],low[v[x][k]]);
                if(lev[x]<=low[v[x][k]])
                    add(x,v[x][k]);
            }
            else
                low[x]=min(low[x],lev[v[x][k]]);
        }
}
int main()
{
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    df(1);
    g<<nr<<'\n';
    for(i=1; i<=nr; i++)
    {
        for(j=0; j<ans[i].size(); j++)
            g<<ans[i][j]<<' ';
        g<<'\n';
    }
}