Cod sursa(job #3140265)

Utilizator proflaurianPanaete Adrian proflaurian Data 5 iulie 2023 09:14:37
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> v[100010],Q[200010];
int n,m,i,j,k,c,top,niv[100010],up[100010],x[200010],y[200010],ST[2000010];
void DF(int,int);
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    for(scanf("%d%d",&n,&m);m;m--)
    {
        scanf("%d%d",&x[m],&y[m]);
        v[x[m]].push_back(m);
        v[y[m]].push_back(m);
    }
    for(k=1;k<=n;k++)
        if(!niv[k])
            DF(k,0);
    printf("%d\n",c);
    for(k=0;k<c;k++)
    {
        for(vector<int>::iterator it=Q[k].begin();it!=Q[k].end();it++)printf("%d ",*it);
        printf("\n");
    }
    return 0;
}
void DF(int nod,int tata)
{
    int vecin;
    niv[nod]=up[nod]=niv[tata]+1;
    for(vector<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
    {
        vecin=x[*it]+y[*it]-nod;
        if(vecin==tata)continue;
        if(!niv[vecin])
        {
            ST[++top]=x[*it];ST[++top]=y[*it];
            DF(vecin,nod);
            up[nod]=min(up[nod],up[vecin]);
            if(up[vecin]>=niv[nod])
            {
                for(i=top-1,j=top;;i-=2,j-=2)
                    if(ST[i]==x[*it]&&ST[j]==y[*it])
                        break;
                sort(ST+i,ST+top+1);Q[c].push_back(ST[i]);
                for(j=i+1;j<=top;j++)
                    if(ST[j]-ST[j-1])
                    Q[c].push_back(ST[j]);
                top=i-1;c++;
            }
        }
        else
        up[nod]=min(up[nod],up[vecin]);
    }
}