Cod sursa(job #1870577)

Utilizator raduzxstefanescu radu raduzx Data 6 februarie 2017 19:10:25
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct nod
{
    int val;
    nod *urm;
};
typedef nod *pnod;
pnod p,v[100003];
struct segm
{
    int x,y;
};
segm muchie[400003];
void ad(int x,int y)
{
    p=new nod;
    p->val=y;
    p->urm=v[x]->urm;
    v[x]->urm=p;
}
int ind[100003],mind[100003],comp[400003],cate,inc,ct,index,ss;
int t[100003];
void dfs(int i)
{
    index+=1;
    ss+=1;
    ind[i]=index;
    mind[i]=index;
    muchie[ss].x=i;
    pnod p;
    p=v[i]->urm;
    while(p)
    {
        if(ind[p->val]!=0)
        {
            if(t[i]!=p->val and mind[i]>ind[p->val])
                mind[i]=ind[p->val];
        }
        else
        {
            muchie[ss].y=p->val;
            t[p->val]=i;
            dfs(p->val);
            if(mind[i]>mind[p->val])
                mind[i]=mind[p->val];
            if(ind[i]<=mind[p->val])
            {
                cate+=1;
                ct+=1;
                inc=ct;
                while(muchie[ss].x!=i and muchie[ss].y!=p->val)
                {
                    comp[ct]=muchie[ss].x;
                    ct+=1;
                    ss-=1;
                }
                comp[ct]=i;
                ct+=1;
                /*comp[ct]=p->val;
                ct+=1;*/
                sort(comp+inc,comp+ct);
            }
        }
        p=p->urm;
    }
}
int main()
{
    int i,j,x,y,n,m;
    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<<cate<<'\n';
    j=1;
    for(i=1;i<=cate;i++)
    {
        while(comp[j]!=0)
        {
            g<<comp[j]<<" ";
            j+=1;
        }
        j+=1;
        g<<'\n';
    }
    return 0;
}