Pagini recente » Cod sursa (job #2054973) | Cod sursa (job #2936755) | Cod sursa (job #2718442) | Cod sursa (job #873198) | Cod sursa (job #11359)
Cod sursa(job #11359)
#include <stdio.h>
#define NMAX 4098
#define MMAX 1 << 16
FILE *f = fopen("triplete.in","rt"), *g = fopen("triplete.out","wt");
struct lista{long int nod;
lista *urm;} *vf[NMAX];
long int n,m,a[NMAX][300],k,x,y,much[MMAX][2],ymax,nr[MMAX],i,j;
int muc(long int x, long int y)
{
lista *p;
p=new lista;
p=vf[x];
while (p)
{if (p->nod==y) return 1;
p=p->urm;
}
return 0;
}
void citire()
{
fscanf(f,"%ld %ld",&n,&m);
lista *p;
for (i=1;i<=m;i++)
{fscanf(f,"%ld %ld",&x,&y);
much[i][0]=x;
much[i][1]=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;
}
for (i=1;i<=n;i++)
{
k=16;
y=1;
while (k<=m+16)
{x=1;
x=(x<<1) + muc(i,k);
for (j=k-1;j%16;j--)
x=(x << 1) + muc(i,j);
a[i][y]=x;
y++;
k+=16;}
}
ymax=y-1;
}
void solve()
{
long int x,y,sol,s;
sol=0;
for (i=1;i<=m;i++)
{
s=0;
x=much[i][0];
y=much[i][1];
for (j=1;j<=ymax;j++)
s+=nr[a[x][j]&a[y][j]];
sol+=s-1;
}
fprintf(g,"%ld",sol/3);
}
int main()
{
citire();
for (i=1;i <= (1 << 17) - 1;i++)
nr[i]=nr[i/2]+i%2;
solve();
fclose(f);
fclose(g);
return 0;
}