Cod sursa(job #1846526)

Utilizator ASTELOTudor Enescu ASTELO Data 13 ianuarie 2017 10:13:33
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include<cstdio>
#include<vector>
using namespace std;
struct eu{int x,y;};
eu st[100001];
vector<int> v[100001],vcc[100001];
int i,n,j,q1,m,nr,pc,cate,viz[100001],niv[100001],l[100001],marc[100001],tata[1000001],vc[100001],x,y,rad,cc;
void dfs(int nod)
    {
    viz[nod]=1;
    l[nod]=niv[nod];
    for(int i=0;i<v[nod].size();i++)
        {
        int f=v[nod][i];
        if(viz[f]==1)
            {
            if(f!=tata[nod]&&l[nod]>niv[f])
                {
                l[nod]=niv[f];
                q1++;
                vcc[q1].push_back(st[cate].y);
                while(st[cate].x!=f)
                    {
                    vcc[q1].push_back(st[cate].x);
                    cate--;
                    }
                vcc[q1].push_back(f);
                cate--;
                }
            }
        else
            {
            if(nod==rad)
                nr++;
            niv[f]=niv[nod]+1;
            st[++cate].x=nod;
            st[cate].y=f;
            tata[f]=nod;
            dfs(f);
            if(l[nod]>l[f])
                l[nod]=l[f];
            if(l[f]>=niv[nod])
                marc[nod]=1;
            }
        }
    }
int main ()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
    {
    scanf("%d%d",&x,&y);
    v[x].push_back(y);
    v[y].push_back(x);
    }
for(i=1;i<=n;i++)
    if(viz[i]==0)
        {
        rad=i;
        niv[i]=1;
        vc[++cc]=i;
        nr=0;
        dfs(i);
        if(nr>=2)
            marc[i]=1;
        else
            marc[i]=0;
        }
printf("%d\n",q1+cate);
for(int i=1;i<=q1;i++)
    {
    for(j=0;j<vcc[i].size();j++)
        printf("%d ",vcc[i][j]);
    printf("\n");
    }
for(int i=1;i<=cate;i++)
    {
    printf("%d %d",st[i].x,st[i].y);
    printf("\n");
    }
return 0;
}