Cod sursa(job #2217308)

Utilizator unknownpersonBidasca Carina Georgiana unknownperson Data 29 iunie 2018 22:54:49
Problema Componente biconexe Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
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()
{
    f>>n>>m;
    for(;m;m--)
    {
        f>>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);
    g<<c<<"\n";
    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]);
    }
}