Cod sursa(job #1692232)

Utilizator vancea.catalincatalin vancea.catalin Data 20 aprilie 2016 15:12:35
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define DX 200100
using namespace std;
fstream fin("biconex.in",ios::in),fout("biconex.out",ios::out);
int nr[DX],low[DX],art[DX],ap[DX],ind=0,n,m,nrc=0;
vector <int> v[DX];
vector <int> r[DX];
stack <pair<int,int> > st;
void citire()
{
    int a,b,i;
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);}
    for(i=1;i<=n;i++) low[i]=nr[i]=-1;
}
void scrie(int nod,int x)
{
    int a,b;
    nrc++;
    //cout<<"comp conexa: "<<nrc<<"\n";
    do
    {
        a=st.top().first; b=st.top().second;
        if(ap[a]!=nrc) r[nrc].push_back(a);
        if(ap[b]!=nrc) r[nrc].push_back(b);
        ap[a]=ap[b]=nrc;
        //cout<<a<<" "<<b<<"\n";
        st.pop();
    }while(!st.empty() && (a!=nod || b!=x));
}
void biconex(int nod,int parinte)
{
    int i,x;
    nr[nod]=low[nod]=++ind;
    for(i=0;i<v[nod].size();i++)
    {
        x=v[nod][i];
        if(x!=parinte)
        {
            if(nr[x]<nr[nod])
            {
                st.push(make_pair(nod,x));
            }
            if(low[x]==-1)
            {
                biconex(x,nod);
                low[nod]=min(low[nod],low[x]);
                if(low[x]>=nr[nod]) //punct de articulatie
                {
                    scrie(nod,x);
                    art[nod]=1;
                }
            }
            else
            {
                low[nod]=min(low[nod],nr[x]);
            }
        }
    }
}
int main()
{
    citire();
    biconex(1,-1);
    fout<<nrc<<"\n";
    for(int i=1;i<=nrc;i++)
    {
        for(int j=0;j<r[i].size();j++)
            fout<<r[i][j]<<" ";
        fout<<"\n";
    }
}