Cod sursa(job #1714915)

Utilizator ZimmyZimmermann Erich Zimmy Data 9 iunie 2016 18:06:44
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define NV 100010
#define NE 200010

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> v[NV],C[NV];
int n,m,c,x[NE],y[NE],N[NV],U[NV],ST[2*NE],top;
void DFS(int,int);
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x[i]>>y[i];
        v[x[i]].push_back(i);
        v[y[i]].push_back(i);
    }
    for(int k=1;k<=n;k++)
        if(!N[k])
            DFS(k,0);
    g<<c<<'\n';
    for(int i=0;i<c;i++)
    {
        for(auto it:C[i])
            g<<it<<' ';
        g<<'\n';
    }
    return 0;
}
void DFS(int nod,int tata)
{
    N[nod]=U[nod]=N[tata]+1;
    int i,j,vec;
    for(auto it:v[nod])
    {
        vec=x[it]+y[it]-nod;
        if(vec==tata)continue;
        if(!N[vec])
        {
            ST[++top]=nod;
            ST[++top]=vec;
            DFS(vec,nod);
            U[nod]=min(U[nod],U[vec]);
            if(U[vec]>=N[nod])
            {
                for(j=top,i=top-1;(ST[j]!=vec)||(ST[i]!=nod);j-=2,i-=2);
                sort(ST+i,ST+top+1);
                C[c].push_back(ST[i]);
                for(;j<=top;j++)
                    if(ST[j]!=ST[j-1])
                        C[c].push_back(ST[j]);
                c++;
                top=i-1;

            }
        }
        else
            U[nod]=min(U[nod],U[vec]);
    }
}