Cod sursa(job #7128)

Utilizator devilkindSavin Tiberiu devilkind Data 21 ianuarie 2007 12:40:38
Problema Triplete Scor 60
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 1.27 kb
#include <stdio.h>
#define NMAX 4098

FILE *f = fopen("triplete.in","rt"), *g = fopen("triplete.out","wt");

struct lista{long int nod;
             lista *urm;} *vf[NMAX];     

long int n,i,j,k,nrt,h[NMAX],hc[NMAX],m,hash[NMAX],nrp[NMAX];

void citire()
{
long int x,y;
lista *p;
fscanf(f,"%ld %ld",&n,&m);
for (i=1;i<=m;i++)
    {fscanf(f,"%ld %ld",&x,&y);
    p=new lista;
    p->nod=x;
    p->urm=vf[y];
    vf[y]=p;
    
    p=new lista;
    p->nod=y;
    p->urm=vf[x];
    vf[x]=p;
    }
}


void BF(long int x)
{
long int cd[NMAX],final,i,j,s;
long int ok;
lista *p;
cd[1]=x;
for (i=1;i<=n;i++)
	hc[i]=h[i];
hc[x]=1;
final=1;
p=vf[x];
s=0;

while (p)
    {if (!hc[p->nod]) {hc[p->nod]=1;cd[++final]=p->nod;}
    p=p->urm;}
    
for (i=1;i<=n;i++)
    {hash[i]=0;nrp[i]=0;}
    
for (i=2;i<=final;i++)
        {
        p=vf[cd[i]];
        hash[cd[i]]++;
        while (p)
              {
              if (p->nod!=x) nrp[p->nod]++;
              p=p->urm;
              }
        }
for (i=1;i<=n;i++)
    nrt=nrt+hash[i]*nrp[i];
}

void solve()
{
nrt=0;
for (i=1;i<=n;i++)     
    {BF(i);
    h[i]=1;}
fprintf(g,"%ld",nrt/2);
}


int main()
{
citire();   
solve();
fclose(f);
fclose(g);
return 0;   
}