【NOIp模拟】【二分图or并查集】GoToandPlay

it2025-01-11  17

Description

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

Input

第一行两个数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 (){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); 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

最新回复(0)