Pagini recente » Cod sursa (job #1727557) | Cod sursa (job #1079522) | Cod sursa (job #1659475) | Cod sursa (job #616266) | Cod sursa (job #215451)
Cod sursa(job #215451)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define maxm 65536 * 2 + 4
#define maxn 4100
long v[maxm], next[maxm], first[maxn], t[maxm], list[maxn], nr[maxn], start[maxn], ok[maxn], i, n, m, a, b, last;
int cmp(const void *a, const void *b) {
return *(long *)a - *(long *)b;
}
long calc(long a, long b) {
long i, val = 0;
long x = start[a], y = start[b];
for (i = x; i < x + nr[a]; ++i) {
if (t[i] > b) {
++ok[t[i]];
}
}
for (i = y; i < y + nr[b]; ++i) {
if (t[i] > b) {
if(ok[t[i]]) {
++val;
}
}
}
for (i = x; i < x + nr[a]; ++i) {
if(t[i] > b) {
--ok[t[i]];
}
}
return val;
}
int main() {
freopen("triplete.in", "r", stdin);
freopen("triplete.out", "w", stdout);
scanf("%ld %ld", &n, &m);
for (i = 1; i <= m; ++i) {
scanf("%ld %ld", &a, &b);
v[i * 2 - 1] = a;
v[i * 2] = b;
next[i * 2] = first[a];
next[i * 2 - 1] = first[b];
first[a] = i * 2;
first[b] = i * 2 - 1;
}
for (i = 1; i <= n; ++i) {
long poz = 0, x;
memset(list, 0, sizeof(list));
x = first[i];
while (x) {
list[++poz] = v[x];
x = next[x];
}
qsort(list + 1, poz, sizeof(list[0]), cmp);
start[i] = last + 1;
nr[i] = poz;
for (long ii = 1; ii <= poz; ++ii) {
t[++last] = list[ii];
}
}
long s = 0;
for (i = 1; i <= n; ++i) {
for (long j = start[i]; j < start[i] + nr[i]; ++j) {
if (t[j] > i) {
s += calc(i, t[j]);
}
}
}
printf("%ld\n", s);
return 0;
}