Cod sursa(job #1863680)

Utilizator c909073Petrisor Addrian c909073 Data 31 ianuarie 2017 09:17:55
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m;
int lista[200001],urm[200001],inc[100001],sf;
int stiva[100001],lb[100001],adc[100001],capat;
int nr;
int ad=1;
bool vazut[100001];
int retin[200001],cp;

void tarhan(int nod,int ina)
{
    int k=++capat;
    stiva[capat]=nod;
    adc[nod]=ad;
    lb[nod]=ad;
    ad++;
    vazut[nod]=true;
    bool ok=false;
    for(int i=inc[nod];i;i=urm[i])
    {
        ok=false;
        if(!vazut[lista[i]]){
            tarhan(lista[i],nod);
            ok=true;

        }
        if(lista[i]!=ina)
         lb[nod]=min(lb[nod],lb[lista[i]]);
            if(ok)
            {
                if(lb[nod]==adc[nod])
                {
                nr++;

                for(int i=k;i<=capat;i++)
                {
                    cp++;

                   retin[cp]=stiva[i];
                }
                cp++;
                capat=k;
                }
            }
    }

}
int main()
{
    f>>n>>m;
    int x,y;
    for(int i=1;i<=m;i++)
        {
            f>>x>>y;
            lista[++sf]=x;
            urm[sf]=inc[y];
            inc[y]=sf;
            lista[++sf]=y;
            urm[sf]=inc[x];
            inc[x]=sf;
        }
    for(int i=1;i<=n;i++)
      if(!adc[i])
       {
            tarhan(1,0);
       }
        g<<nr<<'\n';
    for(int i=1;i<=cp;i++)
        if(retin[i]!=0)
            g<<retin[i]<<" ";
    else g<<"\n";

    return 0;
}