Description
小松鼠终于吃撑了，她决定逃离这个地方。 我们用一张连通图来表示整个西湖的范围，每棵容小松鼠逗留的树都用 这张图上的一个点来表示。小松鼠能够通过只跳一次互相到达的两棵树用 图上的一条无向边来连接。 吃撑了的小松鼠有些神志不清，每次她连跳两条边之后才会在到达的那 个点上休息。她想知道，是否存在一种连续的跳法，使得她有机会在所有 的树上都休息至少一次。 对于这种跳法，你可以任选起点，允许重复经过边，允许重复经过点。 但是超萌小松鼠是一只有梦想的小松鼠，她有时能够突破自己的极限， 使一些原本无法互相到达的两个点能够通过一次跳跃互相到达。
第一行两个数n,m。n表示点的个数，m表示边的条数 接下来m行，每行两个数xi,yi，表示xi和yi之间能够通过一次跳跃互相到 达。 接下来一行一个数q,表示询问的个数。 接下来q行，其中的第i行每行两个数ai,bi。表示在原图的基础上加上从ai到bi的 边。即成为一张n个点m + 1条边的图。 保证给出的原图是个连通图，1 <= ai,bi,xi,yi <= n。
Output
输出一共q行，对于第i个询问，当在原图的基础上加上ai与bi间的无向边 后，如果小松鼠能够找到一种连续的跳法，使得她有机会在所有的树上至 少休息一次，输出一行“Yes”,否则输出一行“No”。（不包含引号）
Constraints
对于前50%，n,q <= 103 ， m <= 2×103。 对于100%，n,q <= 105， m <= 2×105。
Code（50分TLE）
#include <cstdio>
#include <cstring>
#include <queue>
#define INF 100000000
#define maxn 100000
using namespace std;
int n,m,q,fa[maxn],facpy[maxn];
bool vis[maxn];
vector<int> g[maxn];
int find(
int a){
return fa[a]==a ? a : fa[a]=find(fa[a]);
}
int main (){
freopen(
"in.txt",
"r",stdin);
freopen(
"out.txt",
"w",stdout);
memset(g,
0,
sizeof(g));
scanf(
"%d%d",&n,&m);
for(
int i=
1;i<=m;i++){
int a,b;
scanf(
"%d%d",&a,&b);
g[a].push_back(b); g[b].push_back(a);
}
for(
int i=
1;i<=n;i++) fa[i]=i;
for(
int i=
1;i<=n;i++){
int rt=g[i][
0];
for(
int j=
1;j<(
int)g[i].size();j++){
int cur=g[i][j];
fa[find(cur)]=find(rt);
}
}
memcpy(facpy,fa,
sizeof(fa));
scanf(
"%d",&q);
while(q--){
memcpy(fa,facpy,
sizeof(fa));
int a,b;
bool flag=
1;
scanf(
"%d%d",&a,&b);
g[a].push_back(b); g[b].push_back(a);
int rt=g[a][
0];
for(
int j=
1;j<(
int)g[a].size();j++){
int cur=g[a][j];
fa[find(cur)]=find(rt);
}
int check=find(
1);
for(
int i=
2;i<=n;i++){
if(find(i)!=check){
flag=
0;
break;
}
}
if(flag)
puts(
"Yes");
else puts(
"No");
if(a==b) vis[a]=
0;
g[a].pop_back(); g[b].pop_back();
}
return 0;
}
Code（AC二分图染色）
#include <cstdio>
#include <cstring>
#include <queue>
#define INF 100000000
#define maxn 100000
using namespace std;
int n,m,q,col[maxn];
bool flag=
0;
vector<int> g[maxn];
bool vis[maxn];
void ran(
int num,
int c){
if(vis[num]) {
if(c!=col[num]) flag=
1;
return;
}
vis[num]=
1; col[num]=c;
for(
int i=
0;i<(
int)g[num].size();i++)
ran(g[num][i],(c+
1)&
1);
return;
}
int main (){
scanf(
"%d%d",&n,&m);
for(
int i=
1;i<=m;i++){
int a,b;
scanf(
"%d%d",&a,&b);
g[a].push_back(b); g[b].push_back(a);
}
ran(
1,
0);
scanf(
"%d",&q);
while(q--){
int a,b;
scanf(
"%d%d",&a,&b);
if(flag)
puts(
"Yes");
else{
if(col[a]==col[b])
puts(
"Yes");
else puts(
"No");
}
}
return 0;
}
转载于:https://www.cnblogs.com/leotan0321/p/6081379.html
