Pagini recente » Cod sursa (job #272643) | Arbori Indexati Binar | Cod sursa (job #1808482) | Cod sursa (job #2476614) | Cod sursa (job #1718263)
#include <cstdio>
#define Nmax 65537
#define N2 4097
#define MASK 31
typedef struct {
unsigned int u, v;
} cell;
unsigned int N, M;
cell edge[Nmax]; // prieteniile
unsigned int set[N2][N2 >> 5]; // bitset-ul nostru.
/* Seteaza bitul de pe linia "u", pozitia "v", pe "1". */
void setBit(unsigned int u, unsigned int v) {
set[u][v >> 5] |= (1 << (v & MASK));
}
/* Numara cati biti are numarul "u". */
int cBits(unsigned int u) {
unsigned int count = 0;
while (u) {
u &= u - 1;
count++;
}
return count;
}
int main() {
unsigned int i, j;
freopen("triplete.in","r",stdin);
freopen("triplete.out","w",stdout);
// Citeste relatiile de prietenie.
scanf("%d %d", &N, &M);
for (i = 1; i <= M; i++) {
scanf("%d %d", &edge[i].u, &edge[i].v);
if (edge[i].u > edge[i].v) {
unsigned int tmp = edge[i].u;
edge[i].u = edge[i].v;
edge[i].v = tmp;
}
setBit(edge[i].u, edge[i].v);
}
// Calculeaza numarul de triplete.
unsigned int result = 0, groups = (N >> 5);
for (i = 1; i <= M; i++) {
for (j = 0; j <= groups; j++) {
result += cBits(set[edge[i].u][j] & set[edge[i].v][j]);
}
}
printf("%d\n", result);
return 0;
}