swjtu-oj 1569 离线并查集 - c++编程基础

连通 OR 不连通

Time Limit:1000MS Memory Limit:65536K
Total Submit:51 Accepted:9

Description

给定一个无向图，一共n个点，请编写一个程序实现三种操作：
E x 从原图中删除连接x节点的所有边。
D x y 从原图中删除连接x，y节点的边。
Q x y 询问x，y节点是否连通。

Input

输入只有一组测试数据：
第一行两个数n,m（5<=n<=40000,1<=m<=100000）
接下来m行，每行一对整数 x y （x,y<=n）,表示x,y之间有边相连。保证没有重复的边。
接下来一行一个整数 q（q<=100000）
以下q行每行一种操作，保证不会有非法删除。

Output

按询问次序输出所有Q操作的回答，连通的回答Yes，不连通的回答No。

Sample Input

Sample Output

Yes
Yes
No

Hint

输入数据较多，尽量用scanf和printf代替cin和cout！

Source

中文题意，很简单。

首先把所有的边加进来，记录所有的命令，并且执行所有的删除操作，然后逆序加边，并查集维护，有一个bug，被坑wa一次，就是一条边只能算第一次删除，以后的删除就不存在，例如有三个点，1 2 3 其中1-2,1-3，第一次执行删除1-2边的命令，第二次执行删除与1相连的所有边的命令，则第二次只删除了1-3边，在恢复边时，假如不考虑时间，则第一次恢复了1-2,1-3两条边，显然是错的。

代码：

/* ***********************************************
Author :rabbit
Created Time :2014/3/7 17:12:34
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
                using namespace std; #define INF 0x3f3f3f3f #define eps 1e-8 #define pi acos(-1.0) typedef long long ll; const int maxn=41000; set
                
                  s[maxn],t[maxn]; int fa[maxn]; int find(int x){ if(fa[x]!=x)fa[x]=find(fa[x]); return fa[x]; } void bin(int a,int b){ int fx=find(a); int fy=find(b); if(fx==fy)return; fa[fx]=fy; } struct OP{ char op; int x,y; }pp[110000]; int ans[110000]; map
                 
                   mp; int hash(int x,int y){ if(x>y)swap(x,y); return mp[50000*x+y]; } int shan(int x,int y,int i){ if(x>y)swap(x,y); mp[50000*x+y]=i; } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); int n,m; while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;i++){ fa[i]=i; s[i].clear(); } int tot=0; while(m--){ int u,v; scanf("%d%d",&u,&v); s[u].insert(v); s[v].insert(u); } char op[5]; int Q; scanf("%d",&Q); mp.clear(); set
                  
                   ::iterator it; for(int i=1;i<=Q;i++){ scanf("%s",op); pp[i].op=op[0]; if(pp[i].op=='E'){ scanf("%d",&pp[i].x); int x=pp[i].x; for(it=s[x].begin();it!=s[x].end();it++){ int y=*it; if(hash(x,y))continue; shan(x,y,i); } } else{ scanf("%d%d",&pp[i].x,&pp[i].y); if(pp[i].op=='D')shan(pp[i].x,pp[i].y,i); } } //cout<<"4444"<
                   
                    =1;i--){ if(pp[i].op=='Q'){ int fx=find(pp[i].x); int fy=find(pp[i].y); tot++; if(fx==fy)ans[tot]=1; else ans[tot]=0; } else if(pp[i].op=='D'){ bin(pp[i].x,pp[i].y); } else{ for(it=s[pp[i].x].begin();it!=s[pp[i].x].end();it++){ int x=pp[i].x; int y=*it; if(hash(x,y)==i)bin(x,y); } } } for(int i=tot;i>=1;i--){ if(ans[i])puts("Yes"); else puts("No"); } } return 0; }