[Sdoi2008]Cave 洞穴勘测
Time Limit:10000MS Memory Limit:265536K
Total Submit:19 Accepted:6
Case Time Limit:1000MS
Description
辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。
洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：
如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v
如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v
经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。
然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。
辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。
已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。
Input
第一行为两个正整数n和m，分别表示洞穴的个数和终端机上出现过的指令的个数。
以下m行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s（"Connect”、”Destroy”或者”Query”，区分大小写），之后有两个整数u和v (1≤u, v≤n且u≠v) 分别表示两个洞穴的编号。
Output
对每个Query指令，输出洞穴u和洞穴v是否互相连通：是输出”Yes”，否则输出”No”。（不含双引号）
Sample Input
Sample Output
Hint
数据说明
10%的数据满足n≤1000, m≤20000
20%的数据满足n≤2000, m≤40000
30%的数据满足n≤3000, m≤60000
40%的数据满足n≤4000, m≤80000
50%的数据满足n≤5000, m≤100000
60%的数据满足n≤6000, m≤120000
70%的数据满足n≤7000, m≤140000
80%的数据满足n≤8000, m≤160000
90%的数据满足n≤9000, m≤180000
100%的数据满足n≤10000, m≤200000
保证所有Destroy指令将摧毁的是一条存在的通道
本题输入、输出规模比较大，建议cc++选手使用scanf和printf进行IO操作以免超时
Source
俄。。对于这种裸的维护动态森林的题目也没有神马别的好办法。。要么动态树，要么朴素。。。
我一开始写了半天动态树各种TLE+WA。。。
受不鸟了决定写朴素T_T。。
结果居然可以过囧。。。。
其实就按朴素的办法来实现动态树的方法，对每个节点用F[x]表示它的父亲。。
那么我们需要一些操作。。
Mark_Root(x) 将x设为它子树的根。。这个只要将根到x的路径全部反一下就可以了。。
Find_Root(x) 找到x的根。。。只接找。。。
然后就可以差不多类。。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int maxn=10000+10;
int F[maxn],n,m;
void Clear_List()
{
rep(i,n)F[i]=i;
}
int Find_Root(int u)
{
while(u!=F[u])u=F[u];
return u;
}
bool Query(int u,int v)
{
return Find_Root(u)==Find_Root(v);
}
void Mark_Root(int u)
{
int v=F[u],t;F[u]=u;
while(u!=v)
{
t=F[v];F[v]=u;
u=v;v=t;
}
}
void Connect(int u,int v)
{
Mark_Root(u);
Mark_Root(v);
F[v]=u;
}
void Destroy(int u,int v)
{
Mark_Root(u);
F[v]=v;
}
char c[100];
int main()
{
//freopen("in","r",stdin);
scanf("%d%d",&n,&m);int u,v;
Clear_List();
rep(i,m)
{
scanf(" ");scanf("%s%d%d",c,&u,&v);
u–;v–;
switch(c[0])
{
case ‘Q’:Query(u,v)?puts("Yes"):puts("No");break;
case ‘C’:Connect(u,v);break;
case ‘D’:Destroy(u,v);break;
}
}
}
样例输出1 cave.outNoYesNo样例输出2 cave.outYesNo
样例输入1 cave.in200 5Query 123 127Connect 123 127Query 123 127Destroy 127 123Query 123 127样例输入2 cave.in3 5Connect 1 2Connect 3 1Query 2 3Destroy 1 3Query 2 3
样例输出1 cave.outNoYesNo样例输出2 cave.outYesNo
样例输入1 cave.in200 5Query 123 127Connect 123 127Query 123 127Destroy 127 123Query 123 127样例输入2 cave.in3 5Connect 1 2Connect 3 1Query 2 3Destroy 1 3Query 2 3
