Cod sursa(job #3139728)

Utilizator proflaurianPanaete Adrian proflaurian Data 1 iulie 2023 09:04:29
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int p,q;char b[32010],B[32010];
void inc(){p++;if(p==32000){p=0;fread(b,1,32000,stdin);}}
void rInt(int &x){while(b[p]<'0'||b[p]>'9')inc();x=0;while(b[p]>='0'&&b[p]<='9'){x=10*x+b[p]-'0';inc();}}
void wChar(char c){if(q==32000){fwrite(B,1,32000,stdout);q=0;B[q++]=c;}else B[q++]=c;}
void wInt(int x)
{
    if(x>9)wInt(x/10);
    wChar('0'+x%10);
}
vector<int> v[N],Q[N];
int n,m,i,j,k,c,top,niv[N],up[N],x[N],y[N],ST[N];
void DF(int,int);
int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    rInt(n);
    rInt(m);
    for(;m;m--){rInt(x[m]);rInt(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);
    wInt(c);wChar('\n');
    for(k=0;k<c;k++){for(auto it:Q[k]){wInt(it);wChar(' ');}wChar('\n');}
    fwrite(B,1,q,stdout);
    return 0;
}
void DF(int nod,int tata)
{
    int vec;
    niv[nod]=up[nod]=niv[tata]+1;
    for(auto e:v[nod])
    {
        vec=x[e]+y[e]-nod;
        if(vec==tata)continue;
        if(!niv[vec])
        {
            ST[++top]=x[e];ST[++top]=y[e];
            DF(vec,nod);
            up[nod]=min(up[nod],up[vec]);
            if(up[vec]>=niv[nod])
            {
                for(i=top-1,j=top;;i-=2,j-=2)if(ST[i]==x[e]&&ST[j]==y[e])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[vec]);
    }
}