LiveArchieve 6804 : Group of Strangers

問題リンク:https://icpcarchive.ecs.baylor.edu/external/68/6804.pdf

問題概要：
無向グラフが与えられる
3点を選んだとき、それらの間に1本も辺が存在しないようなものの数を数えろ

解法:
公式解説の通り

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

const int MAX_V = 5010;
int V,E;
vector<int> G[MAX_V];
bool edge[MAX_V][MAX_V];
bool heavy[MAX_V];
int heavyV,heavy_vertex[MAX_V];
typedef pair<int,int> ii;

inline ll nC2(ll n) { return n * ( n - 1LL ) / 2LL; }

bool comp(int a,int b) {
  return (int)G[a].size() > (int)G[b].size();
}

void compute(){
  {
    heavyV = 0;
    int limit = sqrt(E);
    rep(i,V) if( (int)G[i].size() >= limit ) {
      heavy[i] = true;
      heavy_vertex[heavyV++] = i;
    }
  }
  rep(i,V) sort(G[i].begin(),G[i].end(),comp); //重要
  vector<int> dvec;
  rep(i,V) dvec.push_back(i); 
  sort(dvec.begin(),dvec.end(),comp); //重要
  // 3-edge triple
  ll three = 0;
  // heavy - heavy - heavy ( ( E**0.5 ) ** 3 )
  rep(i,heavyV) REP(j,i+1,heavyV) if( edge[heavy_vertex[i]][heavy_vertex[j]] ) {
    REP(k,j+1,heavyV) if( edge[heavy_vertex[i]][heavy_vertex[k]] && edge[heavy_vertex[j]][heavy_vertex[k]] ) {
      ++three;
    }
  }

  // 辺の端点a,bの両方がheavyでないような辺について考える　a < b とする これより、aがheavyならbもheavyなのでこれらは無視する　つまり、aはheavyではないため、E**0.5しかそのようなaは存在しない
  rep(i,V) if( !heavy[i] ) {
    int a = i;
    rep(j,(int)G[i].size()){
      int &b = G[i][j];
      if( (int)G[a].size() >  (int)G[b].size() ) break;
      if( (int)G[a].size() == (int)G[b].size() && a > b ) continue;

      rep(k,V){
        int c = dvec[k];
        if( (int)G[b].size() >  (int)G[c].size() ) break;
        if( (int)G[b].size() == (int)G[c].size() && b > c ) continue;
        if( c == a || c == b ) continue;
        if( edge[a][c] && edge[b][c] ) {
          ++three;
        }
      }
    }
  }

  //cout << "three = " << three << endl;

  // 2-edge triple
  ll two = 0;
  rep(i,V) if( (int)G[i].size() >= 2 ) {
    int degree = (int)G[i].size();
    two += nC2(degree);
  }
  two -= 3LL * three;
  
  //cout << "two = " << two << endl;

  // 1-edge triple
  ll one = 0;
  rep(i,V) if( (int)G[i].size() >= 1 ) {
    int degree = (int)G[i].size();
    one += (ll)degree * (ll)( V - degree - 1 );
  }
  one /= 2LL;
  one -= two;

  //cout << "one = " << one << endl;
  ll ans = ( ( (ll)V * (ll)(V-1) * (ll)(V-2) ) / 6LL ) - ( three + two + one );
  printf("%lld\n",ans);
  //cout << ( ( (ll)V * (ll)(V-1) * (ll)(V-2) ) / 6LL ) - ( three + two + one ) << endl;
}

int main(){
  int T,CNT=1;
  scanf("%d",&T);
  while( T-- ){
    rep(i,V) G[i].clear();
    memset(edge,false,sizeof(edge));
    memset(heavy,false,sizeof(heavy));
    scanf(" %d %d",&V,&E);
    int s,t;
    rep(i,E){
      scanf(" %d %d",&s,&t);
      --s, --t;
      G[s].push_back(t);
      G[t].push_back(s);
      edge[s][t] = edge[t][s] = true;
    }
    printf("Case #%d: ",CNT++);
    compute();
  }
  return 0;
}