Cod sursa(job #1870580)

Utilizator raduzxstefanescu radu raduzx Data 6 februarie 2017 19:12:05
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct nod
{
    int val;
    nod *urm;
};
struct segment
{
    int x,y;
};
segment stiva[400003];
int afis[400010],adafis,total;
typedef nod *pnod;
pnod p,v[100003];
int ind[100003],cur,minim[100003],t[100003],index,ss;
void ad(int x,int y)
{
    p=new nod;
    p->val=y;
    p->urm=v[x]->urm;
    v[x]->urm=p;
}
void dfs(int inc)
{
    index+=1;
    ind[inc]=index;
    minim[inc]=index;
    ss+=1;
    stiva[ss].x=inc;
    pnod p;
    p=v[inc]->urm;
    while(p)
    {
        if(ind[p->val]==0)
        {
            t[p->val]=inc;
            stiva[ss].y=p->val;
            dfs(p->val);
            minim[inc]=min(minim[inc],minim[p->val]);

            if(ind[inc]<=minim[p->val])
            {
                total+=1;
                cur=adafis+1;
                while(stiva[ss].x!=inc and stiva[ss].y!=p->val)
                {
                    adafis+=1;
                    afis[adafis]=stiva[ss].x;
                    ss--;
                }
                adafis+=1;
                afis[adafis]=inc;
               /* adafis+=1;
                afis[adafis]=p->val;*/
                adafis+=1;
                afis[adafis]=0;
                sort(afis+cur,afis+adafis);
            }
        }
        else
            if(t[inc]!=p->val and minim[inc]>ind[p->val])
                minim[inc]=ind[p->val];
        p=p->urm;
    }
}
int main()
{
    int n,m,x,y,i,k;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        ad(x,y);
        ad(y,x);
    }
    for(i=1;i<=n;i++)
    {
        if(ind[i]==0)
        {
            index=0;
            ss=0;
            dfs(i);
        }
    }
    g<<total<<'\n';
    k=1;
    for(i=1;i<=total;i++)
    {
        while(afis[k]!=0)
        {
            g<<afis[k]<<" ";
            k+=1;
        }
        k+=1;
        g<<'\n';
    }
    return 0;
}