# Cod sursa(job #8064)

Utilizator Data 23 ianuarie 2007 19:42:02 Triplete 0 cpp done Arhiva de probleme 1.26 kb
``````
#include <stdio.h>
#define NMAX 4096
#define MMAX 66000
#define B 32
#define P 5

struct per { int x, y; } V[MMAX];

char Nr[1 << (B/2) ];
int A[NMAX][ NMAX/B + 1];
int i, j, N, M, a, b, cfg;
long long rez;

inline void set(int cnf,int x)
{
A[cnf][x>>P] |= 1 << (x & (B-1));
}

void prep()
{
int i;

Nr[0] = 0;

for (i = 0; i < 1 << (B/2); i++)
Nr[i] = Nr[i >> 1] + (i&1);
}

int main()
{
freopen("triplete.in","r",stdin);
freopen("triplete.out","w",stdout);

scanf("%d %d", &N, &M);

if (N == 1) { printf("0\n"); return 0; }
if (N == 2) { printf("0\n"); return 0; }
if (N == 3 && M != 3) { printf("0\n"); return 0;}

rez = 0;

for (i = 1; i <= M; i++)
{
scanf("%d %d", &a, &b);

V[i].x = a;
V[i].y = b;

set(a, b);
set(b, a);
}

prep();

for (i = 1; i <= M; i++)
{
a = V[i].x;
b = V[i].y;

for (j = 0; j <= N/B; j++)
{
cfg = A[a][j] & A[b][j];

if (cfg > 1 << (B/2)) rez += Nr[cfg >> 1] + (cfg&1);
else rez += Nr[cfg];
}
}

printf("%lld\n", rez/3);

return 0;
}
``````