DTOJ3320 GotoAndPlay

• 題目
• • 題目描述
  • 輸入格式
  • 輸出格式
  • 樣例
  • • 樣例輸入
    • 樣例輸出
  • 資料範圍與提示
• 題解

題目

題目描述

小松鼠終于吃撐了，她決定逃離這個地方

我們用一張連通圖來表示整個西湖的範圍，每棵容小松鼠逗留的樹都用這張圖上的一個點來表示。小松鼠能夠通過隻跳一次互相到達的兩棵樹用圖上的一條無向邊來連接配接

吃撐了的小松鼠有些神志不清，每次她連跳兩條邊之後才會在到達的那個點上休息。她想知道，是否存在一種連續的跳法，使得她有機會在所有的樹上都休息至少一次

對于這種跳法，你可以任選起點，允許重複經過邊，允許重複經過點

但是超萌小松鼠是一隻有夢想的小松鼠，她有時能夠突破自己的極限，使一些原本無法互相到達的兩個點能夠通過一次跳躍互相到達

輸入格式

第一行兩個數 n , m n,m n,m， n n n表示點的個數， m m m表示邊的條數

接下來 m m m行，每行兩個數 x i , y i x_i,y_i xi​,yi​，表示 x i x_i xi​和 y i y_i yi​之間能夠通過一次跳躍互相到達

接下來一行一個數 q q q，表示詢問的個數

接下來 q q q行，其中的第 i i i行每行兩個數 a i , b i a_i,b_i ai​,bi​，表示在原圖的基礎上加上從 a i a_i ai​到 b i b_i bi​ 的邊。即成為一張 n n n個點 m + 1 m+1 m+1條邊的圖

保證給出的原圖是個連通圖， 1 ⩽ a i , b i , x i , y i ⩽ n 1 \leqslant a_i,b_i,x_i,y_i \leqslant n 1⩽ai​,bi​,xi​,yi​⩽n

輸出格式

輸出一共 q q q行，對于第 i i i個詢問，當在原圖的基礎上加上 a i a_i ai​與 b i b_i bi​間的無向邊後，如果小松鼠能夠找到一種連續的跳法，使得她有機會在所有的樹上至少休息一次，輸出一行“Yes”，否則輸出一行“No”（不包含引号）

樣例

樣例輸入

2 1
1 2
2
1 1 
1 2
           

樣例輸出

Yes
No
           

資料範圍與提示

對于前 50 % 50\% 50%， n , q ⩽ 1 0 3 , m ⩽ 2 × 1 0 3 n,q \leqslant 10^3,m \leqslant 2 \times 10^3 n,q⩽103,m⩽2×103

對于 100 % 100\% 100%， n , q ⩽ 1 0 5 , m ⩽ 2 × 1 0 5 n,q \leqslant 10^5,m \leqslant 2 \times 10^5 n,q⩽105,m⩽2×105

題解

直接對整個圖進行二分圖染色，那麼松鼠的這種跳法隻允許跳過同一種顔色的節點

是以接下來就很簡單了：隻有在發現全圖能被染成一種顔色或者添加的邊的兩端是同一種顔色，這個詢問才是對的，否則就是錯的

附上代碼：

#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;
}