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

樣例輸入1 cave.in

200 5

Query 123 127

Connect 123 127

Query 123 127

Destroy 127 123

Query 123 127

樣例輸入2 cave.in

3 5

Connect 1 2

Connect 3 1

Query 2 3

Destroy 1 3

Query 2 3

Sample Output

樣例輸出1 cave.out

No

Yes

No

樣例輸出2 cave.out

Yes

No

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指令將摧毀的是一條存在的通道本題輸入、輸出規模比較大，建議c\c++選手使用scanf和printf進行I\O操作以免超時

Solution

• 一顆簡單的LCT 。

• 只需維護連邊、斷邊、判斷兩個點是否在同一集合三個操作即可。

Code

#include<cstdio> #include<algorithm> #include<cctype> using namespace std; const int N=1e4+5; int top; int s[N][2],fa[N],st[N]; bool rev[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline bool pd(int x) {return s[fa[x]][1]==x; } inline bool isroot(int x) {return s[fa[x]][0]^x && s[fa[x]][1]^x; } inline void modify(int x) {if(x) rev[x]^=1,swap(s[x][0],s[x][1]); } inline void down(int x) {if(rev[x]){modify(s[x][0]),modify(s[x][1]);rev[x]=false;} } inline void rotate(int x) {int y=fa[x],w=pd(x);if(s[y][w]=s[x][w^1]) fa[s[x][w^1]]=y;if((fa[x]=fa[y]) && !isroot(y)) s[fa[y]][pd(y)]=x;s[fa[y]=x][w^1]=y; } inline void splay(int x) {for(int y=st[top=1]=x;!isroot(y);y=fa[y]) st[++top]=fa[y];while(top) down(st[top--]);for(int y;!isroot(x);rotate(x))if(!isroot(y=fa[x])) rotate(pd(x)==pd(y)?y:x); } inline void access(int x) {for(int y=0;x;x=fa[y=x]) splay(x),s[x][1]=y; } inline void mkroot(int x) {access(x),splay(x),modify(x); } inline void link(int x,int y) {mkroot(x),fa[x]=y; } inline void cut(int x,int y) {mkroot(x),access(y),splay(y);s[y][0]=fa[x]=0; } inline bool query(int x,int y) {mkroot(x),access(y),splay(y);int z=y;while(s[z][0]) z=s[z][0];return x==z; } int main() {int n=read(),m=read();while(m--){char ch=getchar();while(ch^'Q' && ch^'D' && ch^'C') ch=getchar();if(ch=='D') cut(read(),read()); elseif(ch=='C') link(read(),read()); elseputs(query(read(),read())?"Yes":"No");}return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 2049: [Sdoi2008]Cave 洞穴勘测的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。