[TIOJ 1896][IOI 2014] Game

原題連結

這道題目的思維還是有點難度的，但是code寫起來非常精簡，官方提供的構造解法甚至hasEdge裡只須要寫1行......有興趣的可以到IOI2014網站去膜拜一下。



先觀察一下題目要求：讓對方必須問所有的問題才能得知整張圖是否連通，我們知道對方足夠聰明，所以「無意義」的問題是不會被問的。

何謂無意義呢？就是已經知道答案的問題，例如：
n=3,hasEdge(0,1)=1,hasEdge(1,2)=1 ，那麼此時我們已經輸了，因為有個問題是根本不需要被問的：hasEdge(0,2)。因為我們已經知道0,2連通了，0和2是否有邊連接就不重要了！

方便講解，我們稱遊戲中的圖為G，並構造一張新圖P有著G所有的點，有被詢問過的點對就在P中連一條邊。
假設對方詢問某兩個點x,y是否有一條邊存在，並且在之前的回答中x,y在圖G上分別隸屬於連通分量u,v，那麼我們能夠回答「true」的充要條件是：

P中加上(x,y)這條邊後，u中所有點和v中所有點在P中是個完全圖。

證明相當顯然，因為在u,v合併之後任何內部點對的詢問都是無意義的，所以我們必須保持連通分量在合併之前裡面任何一對點都已經被問過了。

實做上用cnt[i][j]紀錄連通分量i,j之間連了幾條邊，連通關係用disjoint set來維護，完全圖的判斷用size和cnt去做，只要merge的時候維護好那麼答案就會是好的。

//#define LOCAL
#include<bits/stdc++.h>
#include "lib1896.h"
using namespace std;
const int maxn=1500+5;
int n,fa[maxn],size[maxn],cnt[maxn][maxn];
int findset(int x) {return fa[x]==x?x:fa[x]=findset(fa[x]);}
void initialize(int N)
{
    n=N;
    for(int i=0;i<n;i++) fa[i]=i,size[i]=1;
    memset(cnt,0,sizeof cnt);
}
int hasEdge(int x,int y)
{
    int u=findset(x),v=findset(y);
    cnt[u][v]++,cnt[v][u]++;
    assert(cnt[u][v]==cnt[v][u]);
    if(cnt[u][v]==size[u]*size[v])
    {
        fa[v]=u;
        for(int i=0;i<n;i++) cnt[u][i]+=cnt[v][i],cnt[i][u]=cnt[u][i];
        size[u]+=size[v];
        return 1;
    }
    return 0;
}