Pagini recente » Cod sursa (job #3194509) | Cod sursa (job #1708193) | Cod sursa (job #1576699) | Cod sursa (job #2125863) | Cod sursa (job #51696)
Cod sursa(job #51696)
#include <stdio.h>
#include <algorithm>
#include <vector>
#define mmax 65537
#define nmax 4097
#define pb push_back
using namespace std;
vector <int> e[nmax];
const int baza = 30;
int x[mmax],y[mmax],i,j,n,m,sus,next,tot;
int gv[nmax][140],p[baza + 5],crt,start,finish;
void puteri() {
p[0] = 1;
for(i = 1; i <= baza; i++) p[i] = p[i - 1] * 2;
}
int main() {
freopen("triplete.in","r",stdin);
freopen("triplete.out","w",stdout);
puteri();
scanf("%d%d",&n,&m);
for(i = 1; i <= m; i++) {
scanf("%d%d",&x[i],&y[i]);
e[x[i]].pb(y[i]); e[y[i]].pb(x[i]);
}
for(i = 1; i <= n; i++) sort(e[i].begin(),e[i].end());
if(n % baza == 0) sus = n;
else sus = (n / baza + 1) * baza;
for(i = 1; i <= n; i++) {
int p1 = 0;
for(j = 1; j <= sus / baza; j++) {
crt = 0;
start = (j - 1) * baza + 1;
finish = j * baza;
while(p1 < (int)e[i].size() && e[i][p1] <= finish) {
crt += p[finish - e[i][p1]];
p1++;
}
gv[i][++gv[i][0]] = crt;
}
}
tot = 0;
for(i = 1; i <= m; i++)
for(j = 1; j <= gv[x[i]][0]; j++)
tot += __builtin_popcount(gv[x[i]][j] & gv[y[i]][j]);
tot /= 3;
printf("%d\n",tot);
return 0;
}