Cod sursa(job #2144294)

Utilizator DeleDelegeanu Alexandru Dele Data 26 februarie 2018 17:39:40
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <vector>
#include <stack>
#define MAX 100100
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> a[MAX];
vector<vector<int> > sol;
vector<int>::iterator it;
stack<pair<int,int> > st;
int i,j,n,x,y,m,r,nrb;
int comp[MAX],nro[MAX],low[MAX];
bool viz[MAX];
void add(int x,int y)
{
    ++nrb;
    int a,b;
    vector<int> v;
    v.push_back(x);
    v.push_back(y);
    comp[x]=nrb;
    comp[y]=nrb;
    while(st.top().first!=x || st.top().second!=y)
    {
        a=st.top().first;
        b=st.top().second;
        st.pop();
        if(comp[a]!=nrb)
        {
            v.push_back(a);
            comp[a]=nrb;
        }
        if(comp[b]!=nrb)
        {
            comp[b]=nrb;
            v.push_back(b);
        }
    }
    st.pop();
    sol.push_back(v);
}
void biconex(int x,int t)
{
    int fiu;
    low[x]=nro[x];
    viz[x]=1;
    vector<int>::iterator it;
    for(it=a[x].begin() ; it!=a[x].end() ; ++it)
    {
        fiu=*it;
        if(fiu!=t)
        {
            if(!viz[fiu])
            {
                nro[fiu]=nro[x]+1;
                st.push(make_pair(x,fiu));

                biconex(fiu,x);

                low[x]=min(low[x],low[fiu]);
                if(low[fiu]>=nro[x])
                    add(x,fiu);
            }
            else
                low[x]=min(low[x],nro[fiu]);
        }
    }
}
int main()
{
    f>>n>>m;
    for(i=1 ; i<=m ; ++i)
    {
        f>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for(i=1 ; i<=n ; ++i)
        if(!comp[i])
    {
        nro[i]=0;
        biconex(i,0);
    }
    g<<nrb<<'\n';
     for(i=0 ; i<sol.size() ; ++i)
    {
        for(j=0 ; j<sol[i].size() ; ++j)
            g<<sol[i][j]<<" ";
        g<<'\n';
    }
    return 0;
}