连通 OR 不连通（NOJ 1044）

比赛描述

给定一个无向图，一共n个点，请编写一个程序实现两种操作：

D x y 从原图中删除连接x，y节点的边。

Q x y 询问x，y节点是否连通

输入

 

第一行两个数n,m（5<=n<=100000,1<=m<=100000）

接下来m行，每行一对整数 x y （x,y<=n）,表示x,y之间有边相连。保证没有重复的边。

接下来一行一个整数 q（q<=100000）

以下q行每行一种操作，保证不会有非法删除。

输出

 

按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D

样例输入

3 3
1 2
1 3
2 3
5
Q 1 2
D 1 2
Q 1 2
D 3 2
Q 1 2

样例输出

C
C
D

 

题目来源

NUAA

#include<cstdio>
#include<iostream>
#include<cstring>  
#include<map>  
#include<algorithm>
#define M 100007 
using namespace std;   
int n,m,fa[M];  
char ans[M];  
struct node  
{  
    int u, v;  
    bool d;  
};node e[M],q[M];  
map<int, bool> hash;   
int Find(int x)  
{  
    if(fa[x]==x)return x;
    return fa[x]=Find(fa[x]); 
}   
void Union(int a, int b)  
{  
    int r1=Find(a);  
    int r2=Find(b);  
    if(r1!=r2) fa[r2]=r1;
}  
int main()  
{  
    for(int i=1;i<=M;i++)fa[i]=i; 
    scanf("%d%d",&n,&m);  
    for(int i=1;i<=m;i++)
    {  
        scanf("%d%d",&e[i].u,&e[i].v);  
        if(e[i].u>e[i].v)  
            swap(e[i].u,e[i].v);  
    }  
    int qnum;    
    scanf("%d",&qnum);  
    for(int i=1;i<=qnum;i++)  
    {  
        char f;
        cin>>f;
        scanf("%d%d",&q[i].u,&q[i].v);  
        if(q[i].u>q[i].v)
            swap(q[i].u,q[i].v);  
        if(f=='D')//将需要删除的边打上标记 
        {  
            q[i].d=true;  
            hash[q[i].u*M+q[i].v]=true;  
        }  
        else  q[i].d=false;  
    }  
    for(int i=1;i<=m;i++)//合并不需要删除的边 
        if(!hash[e[i].u*M+e[i].v])  
            Union(e[i].u,e[i].v);  
    int cnt=0;  
    for(int i=qnum;i>=1;i--)//倒序操作 
    {  
        //将需要删除的边合并，因为在删除之前它是连通的 
        if(q[i].d)Union(q[i].u,q[i].v); 
        else  
        {  
            if(Find(q[i].u)==Find(q[i].v))  
                ans[++cnt]='C';  
            else  
                ans[++cnt]='D';  
        }  
    }  
    for(int i=cnt;i>=1;i--)  
      printf("%c
", ans[i]);  
}