题目

题目描述

小松鼠终于吃撑了，她决定逃离这个地方
我们用一张连通图来表示整个西湖的范围，每棵容小松鼠逗留的树都用这张图上的一个点来表示。小松鼠能够通过只跳一次互相到达的两棵树用图上的一条无向边来连接
吃撑了的小松鼠有些神志不清，每次她连跳两条边之后才会在到达的那个点上休息。她想知道，是否存在一种连续的跳法，使得她有机会在所有的树上都休息至少一次
对于这种跳法，你可以任选起点，允许重复经过边，允许重复经过点
但是超萌小松鼠是一只有梦想的小松鼠，她有时能够突破自己的极限，使一些原本无法互相到达的两个点能够通过一次跳跃互相到达

输入格式

第一行两个数$n,m$，$n$表示点的个数，$m$表示边的条数
接下来$m$行，每行两个数$x_i,y_i$，表示$x_i$和$y_i$之间能够通过一次跳跃互相到达
接下来一行一个数$q$，表示询问的个数
接下来$q$行，其中的第$i$行每行两个数$a_i,b_i$，表示在原图的基础上加上从$a_i$到$b_i$ 的边。即成为一张$n$个点$m+1$条边的图
保证给出的原图是个连通图，$1 \leqslant a_i,b_i,x_i,y_i \leqslant n$

输出格式

输出一共$q$行，对于第$i$个询问，当在原图的基础上加上$a_i$与$b_i$间的无向边后，如果小松鼠能够找到一种连续的跳法，使得她有机会在所有的树上至少休息一次，输出一行“Yes”，否则输出一行“No”（不包含引号）

样例

样例输入

样例输出

1
2

Yes
No

数据范围与提示

对于前$50\%$，$n,q \leqslant 10^3,m \leqslant 2 \times 10^3$
对于$100\%$，$n,q \leqslant 10^5,m \leqslant 2 \times 10^5$

题解

直接对整个图进行二分图染色，那么松鼠的这种跳法只允许跳过同一种颜色的节点
所以接下来就很简单了：只有在发现全图能被染成一种颜色或者添加的边的两端是同一种颜色，这个询问才是对的，否则就是错的
附上代码：

#include<cstdio>
int n,m,q,tot,flag,head[100010],to[400010],nxt[400010],t[400010];
void add(int u,int v)
{
    nxt[++tot]=head[u],head[u]=tot,to[tot]=v;
}
void dfs(int u,int ty)
{
    t[u]=ty;
    for(int i=head[u];i;i=nxt[i]){
        if(t[to[i]]<0) dfs(to[i],(ty+1)%2);
        else if(t[to[i]]==ty) flag=1;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    for(int i=1;i<=n;i++) t[i]=-1;
    dfs(1,0);
    scanf("%d",&q);
    for(int i=1,x,y;i<=q;i++){
        scanf("%d%d",&x,&y);
        if(flag||t[x]==t[y]) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}