题解 P5884 【[IOI2014]game 游戏】

· · 题解

这是一道构造题

构造出来后巨水，但要是想不到就GG

不妨将这个图考虑成树，只有当树上的每条边都被询问后才知道这棵树是否联通

那我们现在尽量让树的边最后被询问到就行了

也就是说我们让每个点最后被询问到的边成为树边就ok了

比如下面这张图，红色的边为每个点最后被询问到的边，红边就构成了一棵生成树

下面考虑代码实现，n 个节点的完全图中有 \frac{n(n-1)}{2} 条边，考虑以 0 为根，第 i 个点的父亲规定只能是编号比 i 小的点，显然这样的边有 i 条，如此总边数依然是 \frac{n(n-1)}{2}

那么对于这 i 条边，我们保留最后出现的那一条的端点为 i 的父亲。这样的话，只有到第 \frac{n(n-1)}{2} 个询问，我们才能知道最后一个点的父亲，才能确定图的联通性。

代码真的很短。。。

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

int n,r,u,v;
int deg[1005];

int main(void)
{
    scanf("%d",&n);
    r=n*(n-1)>>1;
    while(r--)
    {
        scanf("%d%d",&u,&v);
        if(u<v) swap(u,v);
        printf("%d\n",++deg[u]==u);
    }
    return 0;
}