SRM 682 Div1 easy : SmilesTheFriendshipUnicorn

問題概要 :
N人の人がいて、それらの人は0からN-1まで順に番号が割り振られている
これらの人の間には友好関係があり、これは２つの整数で表される
友好関係は2つの配列A,Bとして表されA[i]番の人とB[i]番の人は友達である
A[i] != B[i]
これらの友好関係は無向グラフとして表すことができる
このとき、任意の２頂点間には必ずパスが存在する
このグラフ内に長さが４のパスが存在するか、YESかNOで答えよ
つまり、5つの異なる頂点a,b,c,d,eについて、
aとb,bとc,cとd,dとeに辺が存在する

解法 :
無向グラフ内から下の図のような部分が存在するかを判定したい

このとき、

すぐ上の図の赤い枠で囲まれた辺をループで愚直に決めてしまう
赤い枠で囲まれた辺は２本しかないので、2000 * 2000 で４つの頂点からなる長さ３のパスを求めることができる
残り１つの頂点は長さ３のパスの両端点について、次数からO(1)で計算できる

まず２つの辺から長さ３のパスを計算する

以下の４通りのパスが存在する

この各４通りのパスについて、端点に１つ頂点が追加できれば求めたいパスになる
これは次数からO(1)で計算できる
先ほどの１つめの例で考えると、

2番か4番の頂点から5番に辺があれば良い
2番の頂点に注目したとき、5番の頂点というのは1,3,4番の頂点でなければどれでもよい
つまり、２番の頂点の次数をdegとしたとき、
2-1に辺は必ず存在するので --deg
2-3に辺が存在するなら --deg
2-4に辺が存在するなら --deg
この結果が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 IINF = INT_MAX;
const string kzy = "Yay!";
const string KT  = ":(";

struct Edge {
  int s,t;
  bool operator < (const Edge& e) const {
    if( s != e.s ) return s < e.s;
    return t < e.t;
  }
};

bool rel[2010][2010];
vector<int> G[2010];

class SmilesTheFriendshipUnicorn {
public:

  bool check(Edge e1,Edge e2,bool sp1,bool sp2) {
    int p1 = -1, p2 = -1;
    int rp1 = -1, rp2 = -1;
    if( sp1 ) p1 = e1.t, rp1 = e1.s;
    else      p1 = e1.s, rp1 = e1.t;
    if( sp2 ) p2 = e2.t, rp2 = e2.s;
    else      p2 = e2.s, rp2 = e2.t;
    if( !rel[p1][p2] ) return false;
    
    int deg1 = (int)G[rp1].size();
    int deg2 = (int)G[rp2].size();
    
    //
    --deg1;
    if( rel[rp1][p2] ) --deg1;
    if( rel[rp1][rp2] ) --deg1;
    if( deg1 >= 1 ) return true;
    
    //
    --deg2;
    if( rel[rp2][p1] ) --deg2;
    if( rel[rp2][rp1] ) --deg2;
    if( deg2 >= 1 ) return true;
    
    return false;
  }

   string hasFriendshipChain( int N, vector <int> A, vector <int> B ) {
     N = N;
     vector<Edge> vec;
     rep(i,(int)A.size()) {
       vec.push_back((Edge){A[i],B[i]});
       G[A[i]].push_back(B[i]);
       G[B[i]].push_back(A[i]);
       rel[A[i]][B[i]] = rel[B[i]][A[i]] = true;
     }
     rep(i,(int)vec.size()) {
       Edge &e1 = vec[i];
       rep(j,(int)vec.size()) {
         Edge &e2 = vec[j];
         if( e1.s == e2.s || e1.s == e2.t ) continue;
         if( e1.t == e2.s || e1.t == e2.t ) continue;
         if( check(e1,e2,0,0) ) return kzy;
         if( check(e1,e2,0,1) ) return kzy;
         if( check(e1,e2,1,0) ) return kzy;
         if( check(e1,e2,1,1) ) return kzy;
       }
     }
     
     return KT;
   }
};