Cod sursa(job #1303258)

Utilizator danyro364Savu Ioan Daniel danyro364 Data 27 decembrie 2014 19:54:55
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
//#include <iostream>
#include <cstdio>
#include <vector>
#define nmax 100001
using namespace std;
FILE *f=fopen("biconex.in","r"),*g=fopen("biconex.out","w");
vector <int> l[nmax],r[nmax];
int n,art[nmax],k,dfn[nmax],low[nmax],nd,nrc,nrsol;
struct per{
    int x,y;
}sol[nmax];
inline int mini(int a, int b)
{
    if(a<b)
        return a;
    return b;
}
void afis(int x, int u)
{
    nrsol++;
    do{
        //fprintf(g,"%d %d - ",sol[k].y,sol[k].x);
        if(art[sol[k].y]!=nrsol)
        {
            art[sol[k].y]=nrsol;
            r[nrsol].push_back(sol[k].y);
        }
        if(art[sol[k].x]!=nrsol)
        {
            art[sol[k].x]=nrsol;
            r[nrsol].push_back(sol[k].x);
        }
        --k;

    }while(sol[k+1].y!=x||sol[k+1].x!=u);
}
void biconex(int u, int tu)
{
    dfn[u]=low[u]=++nd;
    int i,j,x;
    for(i=0;i<l[u].size();i++)
    {
        x=l[u][i];
        if(x!=tu&&dfn[x]<dfn[u])
        {
            ++k;
            sol[k].x=u;
            sol[k].y=x;
        }
        if(dfn[x]==-1)
        {
            if(u==1)
                nrc++;
            biconex(x,u);
            low[u]=mini(low[u],low[x]);
            if(low[x]>=dfn[u])
            {
                /*if(x!=1)
                    art[u]=1;*/
                afis(x,u);
            }
        }
        if(dfn[x]!=-1&&x!=tu)
            low[u]=mini(low[u],dfn[x]);

    }
}
int main()
{
    int i,j,m,x,y;
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d",&x,&y);
        l[x].push_back(y);
        l[y].push_back(x);
    }
    fclose(f);
    for(i=1;i<=n;i++)
        dfn[i]=low[i]=-1;
    biconex(1,-1);
    fprintf(g,"%d\n",nrsol);
    for(i=1;i<=nrsol;i++)
    {
        for(j=0;j<r[i].size();j++)
            fprintf(g,"%d ",r[i][j]);
        fprintf(g,"\n");
    }
    fclose(g);
    /*if(nrc>1)
        art[1]=1;*/
    return 0;
}