Pagini recente » Cod sursa (job #157790) | Cod sursa (job #2822668) | Cod sursa (job #2404136) | Cod sursa (job #2355983) | Cod sursa (job #7607)
Cod sursa(job #7607)
#include <stdio.h>
#include <stdlib.h>
#define MAXN (1 << 12)
#define swap(a,b) ((a)^=(b), (b)^=(a), (a)^=(b))
typedef unsigned int int_;
const int F = (1<<16)-1;
int N, M;
int_ G[MAXN][MAXN>>5];
int *V[MAXN], deg[MAXN];
int res, cnt[1<<16];
void baga(int_ u, int_ v)
{
G[u][v>>5] |= (1 << (v & 31));
}
int bits(int_ x)
{
return cnt[x&F]+cnt[(x>>16)&F];
}
int count(int x, int y)
{
int i, r = 0;
for(i = 0; i <= (N>>5); i++)
r += bits(G[x][i]&G[y][i]);
return r;
}
void solve(void)
{
int i, x, y, *p;
for(i = 1; i < (1<<16); i++)
cnt[i] = cnt[i>>1] + (i&1);
for(x = 0; x < N; x++)
for(p = V[x]; *p; p++)
res += count(x, *p);
}
int edge[1<<17][2];
void read_data(void)
{
int i, u, v;
scanf("%d %d\n", &N, &M);
for(i = 1; i <= M; i++)
{
scanf("%d %d\n", &u, &v);
if(u > v) swap(u, v);
u--, v--;
baga(u, v);
deg[u]++;
edge[i][0] = u, edge[i][1] = v;
}
for(i = 0; i < N; i++)
V[i] = (int*) malloc(sizeof(int)*(deg[i]+2)), V[i][deg[i]] = 0,
deg[i] = 0;
for(i = 1; i <= M; i++)
{
u = edge[i][0], v = edge[i][1];
V[u][deg[u]++] = v;
}
}
void write_data(void)
{
printf("%d\n", res);
}
int main(void)
{
freopen("triplete.in", "rt", stdin);
freopen("triplete.out", "wt", stdout);
read_data();
solve();
write_data();
return 0;
}