Cod sursa(job #1963780)

Utilizator ana-maria.simiAna-Maria Simionescu ana-maria.simi Data 12 aprilie 2017 19:27:06
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int k,vfst,dfn[100001],low[100001],num,start,nrfii,n,m,q,w;
bool viz[100001];
struct muchie {int tata,fiu;}st[100001];
vector <int> sol[100001],L[100001];

void Afisare(int x, int u)
{
    for(int i=1; i<=n; i++)
        viz[i]=0;
    muchie p;
    ++k;
    do{
       p=st[vfst--];
    if(!viz[p.fiu])
       {sol[k].push_back(p.fiu);
       viz[p.fiu]=1;}
    if(!viz[p.tata])
       {sol[k].push_back(p.tata);
       viz[p.tata]=1;}
    }while(p.tata!=u || p.fiu!=x);

}

void Biconex(int u, int tu)
{   int x;
    dfn[u]=low[u]=++num;
    for(int i=0; i<L[u].size(); i++)
    {
        x=L[u][i];
        if(x!=tu && dfn[x]<dfn[u])
        {
            st[++vfst].fiu=x;
            st[vfst].tata=u;
        }
        if(dfn[x]==-1)
        {

            Biconex(x, u);

        low[u]=min(low[x],low[u]);
        if(dfn[u]<=low[x])
        {
            Afisare(x,u);
        }}
        else
            if(x!=tu)
                low[u]=min(low[u],dfn[x]);
    }
}

int main()
{
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
        {scanf("%d%d", &q, &w);
        L[q].push_back(w);
        L[w].push_back(q);
        if(i<=n)
            dfn[i]=low[i]=-1;}
    start=1;
    for(int i=m+1; i<=n; i++)
        dfn[i]=low[i]=-1;
    st[0].fiu=start;
    st[0].tata=-1;
    vfst=0;
    Biconex(start,-1);
    printf("%d\n", k);
    for(int i=1; i<=k; i++)
        {for(int j=0; j<sol[i].size(); j++)
            printf("%d ", sol[i][j]);
        printf("\n");}

    return 0;
}