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#include #include #define INF 100000000#define maxn 100000using namespace std;int n,m,q,fa[maxn],facpy[maxn];bool vis[maxn];vector 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#include #include #define INF 100000000#define maxn 100000using namespace std;int n,m,q,col[maxn];bool flag=0;vector 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;}