남쪽 우편 OJ 1044 연결 OR 연결 되 지 않 음

연결 OR 연결 되 지 않 음
시간 제한(일반/자바) : 
1000 MS/ 3000 MS          실행 메모리 제한:65536 KByte 총 제출:445           테스트 통과:89 
경기 설명
방향 없 는 그림 을 지정 합 니 다.모두 n 개의 점 을 지정 합 니 다.프로그램 을 만들어 두 가지 작업 을 수행 하 십시오.
D x y 원본 그림 에서 x,y 노드 를 연결 하 는 쪽 을 삭제 합 니 다.
Q x y x,y 노드 연결 여부 묻 기
입력
첫 줄 두 개 수 n,m(5<=n<=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

/* 307MS
#include<iostream>
#include<map>
#define MAX_N 100001
using namespace std;

int root[MAX_N];
char result[MAX_N];

struct edge{
	int a,b;
	bool del;
}e[MAX_N],q[MAX_N];

void init(int n){
	for(int i=1;i<=n;i++){
		root[i] = i;
	}
}

int getRoot(int i){
	return root[i]==i ? i : root[i]=getRoot(root[i]);	//TL
}

void Union(int a, int b){
	int ra=getRoot(a),rb=getRoot(b);
	if(ra!=rb){
		root[ra] = root[rb];
	}
}

bool find(int a, int b){
	return getRoot(a)==getRoot(b);
}

int main(){
	int n,m,i,qNum,outNo;
	char cmd[2];
	map<int,bool> willDel;
	scanf("%d%d",&n,&m);
	init(n);
	for(i=0;i<m;i++){
		scanf("%d%d",&e[i].a,&e[i].b);
		if(e[i].a > e[i].b){
			e[i].a ^= e[i].b;
			e[i].b ^= e[i].a;
			e[i].a ^= e[i].b;
		}
	}
	scanf("%d",&qNum);
	for(i=0;i<qNum;i++){
		scanf("%s%d%d",cmd,&q[i].a,&q[i].b);
		if(q[i].a > q[i].b){
			q[i].a ^= q[i].b;
			q[i].b ^= q[i].a;
			q[i].a ^= q[i].b;
		}
		if('D'==*cmd){
			q[i].del = 1;
			willDel[ q[i].a*MAX_N+q[i].b ] = 1;
		}
	}
	for(i=0;i<m;i++){								//          
		if(!willDel[ e[i].a*MAX_N+e[i].b ]){
			Union(e[i].a,e[i].b);
		}
	}
	outNo=0;
	for(i=qNum-1; i>=0; i--){						//    ，          
		if(q[i].del){
			Union(q[i].a,q[i].b);
		}else{
			if( find(q[i].a,q[i].b) ){
				result[outNo++]='C';
			}else{
				result[outNo++]='D';
			}
		}
	}
	for(i=outNo-1;i>=0;i--){
		printf("%c
",result[i]);
	}
}
*/


/*
// 237MS
#include<iostream>
#include<set>
#define MAX_N 100001
using namespace std;

int root[MAX_N];
char result[MAX_N];

struct edge{
	int a,b;
	bool del;
}e[MAX_N],q[MAX_N];

void init(int n){
	for(int i=1;i<=n;i++){
		root[i] = i;
	}
}

int getRoot(int i){
	return root[i]==i ? i : root[i]=getRoot(root[i]);
}

void Union(int a, int b){
	int ra=getRoot(a),rb=getRoot(b);
	if(ra!=rb){
		root[ra] = root[rb];
	}
}

bool find(int a, int b){
	return getRoot(a)==getRoot(b);
}

int main(){
	int n,m,i,qNum,outNo;
	char cmd[2];
	set<int> willDel;
	scanf("%d%d",&n,&m);
	init(n);
	for(i=0;i<m;i++){
		scanf("%d%d",&e[i].a,&e[i].b);
		if(e[i].a > e[i].b){
			e[i].a ^= e[i].b;
			e[i].b ^= e[i].a;
			e[i].a ^= e[i].b;
		}
	}
	scanf("%d",&qNum);
	for(i=0;i<qNum;i++){
		scanf("%s%d%d",cmd,&q[i].a,&q[i].b);
		if(q[i].a > q[i].b){
			q[i].a ^= q[i].b;
			q[i].b ^= q[i].a;
			q[i].a ^= q[i].b;
		}
		if('D'==*cmd){
			q[i].del = 1;
			willDel.insert(q[i].a*MAX_N+q[i].b);
		}
	}
	for(i=0;i<m;i++){								//          
		if(!willDel.count(e[i].a*MAX_N+e[i].b)){
			Union(e[i].a,e[i].b);
		}
	}
	outNo=0;
	for(i=qNum-1; i>=0; i--){						//    ，          
		if(q[i].del){
			Union(q[i].a,q[i].b);
		}else{
			if( find(q[i].a,q[i].b) ){
				result[outNo++]='C';
			}else{
				result[outNo++]='D';
			}
		}
	}
	for(i=outNo-1;i>=0;i--){
		printf("%c
",result[i]);
	}
}
*/




// 229MS
#include<iostream>
#include<set>
#define MAX_N 100001
using namespace std;

int root[MAX_N];
char result[MAX_N];

struct edge{
	int a,b;
	bool del;
}e[MAX_N],q[MAX_N];

void init(int n){
	for(int i=1;i<=n;i++){
		root[i] = i;
	}
}

int getRoot(int i){
	return root[i]==i ? i : root[i]=getRoot(root[i]);
}

void Union(int a, int b){
	int ra=getRoot(a),rb=getRoot(b);
	if(ra!=rb){
		root[ra] = root[rb];
	}
}

bool find(int a, int b){
	return getRoot(a)==getRoot(b);
}

int main(){
	int n,m,i,qNum,outNo;
	char cmd;
	set<int> willDel;
	scanf("%d%d",&n,&m);
	init(n);
	for(i=0;i<m;i++){
		scanf("%d%d",&e[i].a,&e[i].b);
		if(e[i].a > e[i].b){
			e[i].a ^= e[i].b;
			e[i].b ^= e[i].a;
			e[i].a ^= e[i].b;
		}
	}
	scanf("%d",&qNum);
	for(i=0;i<qNum;i++){
		getchar();
		scanf("%c%d%d",&cmd,&q[i].a,&q[i].b);
		if(q[i].a > q[i].b){
			q[i].a ^= q[i].b;
			q[i].b ^= q[i].a;
			q[i].a ^= q[i].b;
		}
		if('D'==cmd){
			q[i].del = 1;
			willDel.insert(q[i].a*MAX_N+q[i].b);
		}
	}
	for(i=0;i<m;i++){								//          
		if(!willDel.count(e[i].a*MAX_N+e[i].b)){
			Union(e[i].a,e[i].b);
		}
	}
	outNo=0;
	for(i=qNum-1; i>=0; i--){						//    ，          
		if(q[i].del){
			Union(q[i].a,q[i].b);
		}else{
			if( find(q[i].a,q[i].b) ){
				result[outNo++]='C';
			}else{
				result[outNo++]='D';
			}
		}
	}
	for(i=outNo-1;i>=0;i--){
		printf("%c
",result[i]);
	}
}