GotoAndPlay
10月3日,在杭州市西湖景区,一只小松鼠不停地接受一道道食物,花生、
玉米、饼干,可谓来者不拒,憨态可掬的模样吸引了众多围观者...
Description
小松鼠终于吃撑了,她决定逃离这个地方。
我们用一张连通图来表示整个西湖的范围,每棵容小松鼠逗留的树都用
这张图上的一个点来表示。小松鼠能够通过只跳一次互相到达的两棵树用
图上的一条无向边来连接。
吃撑了的小松鼠有些神志不清,每次她连跳两条边之后才会在到达的那
个点上休息。她想知道,是否存在一种连续的跳法,使得她有机会在所有
的树上都休息至少一次。
对于这种跳法,你可以任选起点,允许重复经过边,允许重复经过点。
但是超萌小松鼠是一只有梦想的小松鼠,她有时能够突破自己的极限,
使一些原本无法互相到达的两个点能够通过一次跳跃互相到达。
Input
第一行两个数\(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 <= a_i , b_i , x_i , y_i <= n\).
Output
输出一共q行,对于第i个询问,当在原图的基础上加上a i 与b i 间的无向边
后,如果小松鼠能够找到一种连续的跳法,使得她有机会在所有的树上至
少休息一次,输出一行“Yes”,否则输出一行“No” 。 (不包含引号)
Constraints
对于前50%,\(n, q <= 10^3 , m <= 2 × 10^3 。\)
对于100%,\(n, q <= 10^5 , m <= 2 × 10^5 。\)
Solution
二分图染色
用0/1表示两种颜色
如果我们把一个点染成0色,那么与之相连的点就染成1色
那么结合题意,就有这样的性质
如果两个点是一种颜色<=>代表这两个点之间隔了两条边
我们把染成0色的点叫做奇点,染成1色的叫做偶点(这个概念很重要)
特别的,如果我们在染色过程发现一个点已经访问过,那么这个时候这个点已经有了颜色,如果当前要染的颜色与之前不相同,则说明当前这个点既是奇点又是偶点,说明松鼠若以它为起点,既能到达所有奇点,又能到达所有偶点,那么待会无论连哪条边都输出"Yes"
在加边过程中,我们判断一下,相连的两个点是不是颜色相同,如果颜色相同的的话,说明这个点同为奇点或同为偶点,我们如果把它们之间连一条边,那么它们将既是奇点,又是偶点,输出"Yes",否则,对结果没有影响,输出"No"
关于题意的
使一些原本无法互相到达的两个点能够通过一次跳跃互相到达。
以及
保证给出的原图是个连通图
我也很无奈~,只能说这个算法只能适用于连通图,如果是非连通图,我们需要重新建边,dfs便利每个联通块,然后对联通块染色,像之前那样判断
Code
#include<bits/stdc++.h>
#define il inline
#define rg register
#define lol long long
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
using namespace std;
const int N=1e6+10,M=2e5+10;
const int inf=2e9;
int n,m,q,cur,ans;
bool flag;
int to[M<<1],nex[M<<1],head[N];
int col[N];
void in(int &ans)
{
ans=0; int f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') ans=(ans<<1)+(ans<<3)+i-'0', i=getchar();
ans*=f;
}
il void add(int a,int b) {
to[++cur]=b;
nex[cur]=head[a];
head[a]=cur;
}
void work(int u,int c) {
col[u]=c;
for(int i=head[u];i;i=nex[i]) {
if(col[to[i]]==-1) work(to[i],(c+1)%2);
else if(col[to[i]]==c) flag=1;
}
}
int main()
{
freopen("GotoAndPlay.in","r",stdin);
freopen("GotoAndPlay.out","w",stdout);
int x,y; in(n),in(m);
for(int i=1;i<=m;i++) {
in(x); in(y);
add(x,y); add(y,x);
}
memset(col,-1,sizeof(col));
work(1,0); in(q);
for(int i=1;i<=q;i++) {
in(x); in(y);
if(flag) puts("Yes");
else puts(col[x]==col[y]?"Yes":"No");
}
return 0;
}