yukicoder No.488 四角関係

問題

問題概要

ノード間のつながりが与えられる. 任意の4つのノードの組み合わせを考えて, その4つのノード間のつながりだけを考えたときに四角形となっている組み合わせがいくつあるか.

解法

n=50なので, すべての任意の4つの組み合わせの総数nC4を全部計算しても間に合う.
4つのノードが四角形になるかを確かめる方法は, 四角形になるとき, その4頂点すべてはほかの3頂点のうちの2つとつながっている. G[i][j] := 1ならi-j間に辺があり, 0ならi-j間に辺はない
という配列Gを使って計算すればいい.

ミス

すぐに思いつきたい.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int G[55][55];
int n, m;
int main(void){
    cin >> n >> m;
    rep(i, m){
        int a, b; cin >> a >> b;
        G[a][b] = G[b][a] = 1;
    }
    int cnt = 0;
    rep(i, n)reps(j, i + 1, n)reps(k, j + 1, n)reps(l, k + 1, n){
        int d1 = G[i][j] + G[i][k] + G[i][l];
        int d2 = G[j][i] + G[j][k] + G[j][l];
        int d3 = G[k][i] + G[k][j] + G[k][l];
        int d4 = G[l][i] + G[l][j] + G[l][k];
        if(d1 == 2 && d2 == 2 && d3 == 2 && d4 == 2) cnt++;
    }

    printf("%d\n", cnt);
    return 0;
}