Pagini recente » Cod sursa (job #838707) | Cod sursa (job #2088586) | Cod sursa (job #484060) | Cod sursa (job #3210230) | Cod sursa (job #22569)
Cod sursa(job #22569)
#include <stdio.h>
#define N 4100
#define M 135000
int a[M], b[M], x[M], y[M];
void sort(int l, int r);
int main () {
int n, m, i, j, k, l, p[N], q, t;
freopen ("triplete.in", "rt", stdin);
freopen ("triplete.out", "wt", stdout);
scanf ("%d%d", &n, &m);
for (i=0;i<m;i++) {
scanf ("%d%d", &q, &t);
x[i*2]=q; y[i*2]=t;
x[i*2+1]=t; y[i*2+1]=q; }
m=2*m;
x[m]=n+1; y[m]=n+1;
sort (0, m);
p[0]=p[1]=0;
for (i=1;x[i]<=n;i++)
if (x[i]!=x[i+1])
p[x[i+1]]=i+1;
t=0;
for (i=1;i<=n;i++)
for (j=p[i];x[p[i]]==x[j];j++)
for (k=p[y[j]];x[p[y[j]]]==x[k];k++) {
q=0;
for (l=p[y[k]];x[p[y[k]]]==x[l];l++)
if (i==y[l]) {
q=1; break; }
t+=q; }
printf ("%d\n", t/6);
return 0;
}
void sort(int l, int r) {
int c, i, j, k;
if (l==r) return;
c=(l+r)/2;
sort(l, c);
sort(c+1, r);
i=l; j=c+1; k=l;
while (i<=c && j<=r)
if (x[i]<x[j]) {
b[k]=y[i];
a[k++]=x[i++]; }
else {
b[k]=y[j];
a[k++]=x[j++]; }
while (i<=c) { b[k]=y[i]; a[k++]=x[i++]; }
while (j<=r) { b[k]=y[j]; a[k++]=x[j++]; }
for (k=l; k<=r; k++) { x[k]=a[k]; y[k]=b[k]; }
}