Pagini recente » Statistici Duglasjpj (Duglasjpj) | Monitorul de evaluare | Diferente pentru problema/civilizatie intre reviziile 11 si 6 | Istoria paginii utilizator/niculescuteodor | Cod sursa (job #2018544)
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
using namespace std;
#define NMAX 4096
int N;
vector<int> G[NMAX];
bitset<NMAX> A[NMAX];
int ntriangles;
void ReadInput() {
int M;
scanf("%d%d", &N, &M);
for (int i = 0; i < M; ++i) {
int x, y;
scanf("%d%d", &x, &y);
x--; y--;
A[x][y] = A[y][x] = 1;
G[x].push_back(y);
G[y].push_back(x);
}
}
void Solve() {
for (int i = 0; i < N; ++i) sort(G[i].begin(), G[i].end(), greater<int>());
for (int i = 0; i < N; ++i) {
for (const int& j : G[i]) {
if (j <= i) break;
int niter = (G[i].size() < G[j].size()) ? i : j;
int nother = i ^ j ^ niter;
for (const int& x : G[niter]) {
if (x <= nother || x <= niter) break;
ntriangles += A[nother].test(x);
}
}
}
}
void WriteOutput() {
printf("%d\n", ntriangles);
}
int main() {
freopen("triplete.in", "r", stdin);
freopen("triplete.out", "w", stdout);
ReadInput();
Solve();
WriteOutput();
}