Cod sursa(job #2124271)

Utilizator bleo16783FMI Bleotiu Cristian bleo16783 Data 7 februarie 2018 07:54:54
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
#define N 100100
#define mp make_pair
#define f first
#define s second
#define pb push_back
int c[N],niv[N],low[N],i,j,n,x,y,m,r,nr_c,viz[N];
vector<int>a[N];
vector<vector<int> >sol;
stack<pair<int,int> > st;
void add(int x,int y)
{
    ++nr_c;
    int a,b;
    vector<int>curr;
    curr.pb(x);curr.pb(y);
    c[x]=nr_c;c[y]=nr_c;
    while(st.top().f!=x || st.top().s!=y)
    {
        a=st.top().f,b=st.top().s;
        st.pop();
        if(c[a]!=nr_c)
        {
            curr.pb(a);
            c[a]=nr_c;
        }
        if(c[b]!=nr_c)
        {
            c[b]=nr_c;
            curr.pb(b);
        }
    }
    st.pop();
    sol.pb(curr);
}
void df(int k,int t)
{
    int nod;
    low[k]=niv[k];
    viz[k]=1;
    for(int it=0;it<a[k].size();++it)
    {
        nod=a[k][it];
        if(nod!=t)
        {
            if(!viz[nod])
            {
                niv[nod]=niv[k]+1;
                st.push(mp(k,nod));
                df(nod,k);
                low[k]=min(low[k],low[nod]);
                if(low[nod]>=niv[k])
                    add(k,nod);
            }
            else
                low[k]=min(low[k],niv[nod]);
        }
    }
}
int main()
{
    ifstream f("conex.in");
    f>>n>>m;
    for(i=0;i<m;++i)
    {
        f>>x>>y;
        a[x].pb(y);
        a[y].pb(x);
    }
    for(i=1;i<=n;++i)
        if(!c[i])
    {
        niv[i]=0;
        df(i,0);

    }
    ofstream g("conex.out");
    g<<nr_c<<'\n';
    for(i=0;i<sol.size();++i)
    {
        for(j=0;j<sol[i].size();++j)
            g<<sol[i][j]<<" ";
        g<<'\n';
    }
    return 0;
}