Cod sursa(job #151813)
#include <stdio.h>
#define max_n 4096
#define max_m 65537
struct muchie
{
int x, y;
};
char p2[8] = {1,2,4,8,16,32,64,128};
muchie vm[max_m];
char a[max_n+1][max_n/8+1];
int n,m;
inline void adauga_relatie(int x, int y)
{
int grup=y/8+1;
int pozitie_binara = y%8;
a[x][grup]|=p2[8-pozitie_binara];
}
inline void citeste()
{
freopen("triplete.in","r",stdin);
scanf("%d %d\n",&n,&m);
int i,x,y;
for(i=1;i<=m;++i)
{
scanf("%d %d\n",&x,&y);
vm[i].x=x;
vm[i].y=y;
adauga_relatie(x, y);
adauga_relatie(y, x);
}
fclose(stdin);
}
inline int numara_biti_comuni(char a, char b)
{
char z = a&b;
//cati biti de 1 are z?
int nrb=0;
while(z)
{
z=z&(z-1);
nrb++;
}
return nrb;
}
int main()
{
citeste();
int tc=0;
int i,k;
for(k=1;k<=m;++k)
{
for(i=1;i<=n/8+1;++i)
{
tc+=numara_biti_comuni(a[vm[k].x][i], a[vm[k].y][i]);
}
}
freopen("triplete.out","w",stdout);
printf("%d\n",tc/3);
fclose(stdout);
return 0;
}