Cod sursa(job #2018542)

Utilizator Ionut.popescuLiviu Rebreanu Ionut.popescu Data 5 septembrie 2017 12:44:21
Problema Triplete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

#define NMAX 4096

int N;

vector<int> G[NMAX];
bool A[NMAX][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 (int j = i + 1; j < N; ++j) {
            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][x];
            }
        }
    }    
}

void WriteOutput() {
    printf("%d\n", ntriangles);
}

int main() {
    freopen("triplete.in", "r", stdin);
    freopen("triplete.out", "w", stdout);
    
    ReadInput();
    Solve();
    WriteOutput();
}