原題

Description

你應(yīng)該知道無(wú)向圖的連通塊的數(shù)量，你應(yīng)該知道如何求連通塊的數(shù)量。當(dāng)你興奮與你的成就時(shí)，破壞王Alice拆掉了圖中的邊。當(dāng)她發(fā)現(xiàn)，每刪去一條邊，你都會(huì)記下邊的編號(hào)，同時(shí)告訴她當(dāng)前連通塊的個(gè)數(shù)。

然而，對(duì)邊編號(hào)簡(jiǎn)直就是個(gè)悲劇，因?yàn)锳lice為了刁難你，拆掉編號(hào)從l到r的邊，當(dāng)然你需要做的事情就是求連通塊的個(gè)數(shù)。如果你答對(duì)了，Alice會(huì)把拆掉的邊裝好，迚行下一次破壞。如果你無(wú)法完成這個(gè)任務(wù)，Alice會(huì)徹底毀了你的圖。

進(jìn)行完足夠多次之后，Alice覺(jué)得無(wú)聊，就玩去了，而你卻需要繼續(xù)做第三題。

Input

第一行兩個(gè)整數(shù)n,m，表示點(diǎn)數(shù)和邊數(shù)。

之后m行每行兩個(gè)整數(shù)x,y，表示x與y之間有無(wú)向邊。（按讀入順序給邊編號(hào)，編號(hào)從1開(kāi)始）

一行一個(gè)整數(shù)k，表示Alice的破壞次數(shù)。

之后k行，每行兩個(gè)整數(shù)l,r。

Output

k行，每行一個(gè)整數(shù)。

Sample Input

6 5

1 2

5 4

2 3

3 1

3 6

6

1 3

2 5

1 5

5 5

2 4

3 3

Sample Output

4

5

6

3

4

2

Data Constraint

對(duì)于30%的數(shù)據(jù)，n<=100,k<=10

對(duì)于60%的數(shù)據(jù)，k<=1000

對(duì)于100%的數(shù)據(jù)，n<=500,m<=10000,k<=20000,1<=l<=r<=m

題解

• 并查集。Collect!

• 每一個(gè) f[i] 為一個(gè)并查集，記錄只添加前 i 條邊時(shí)，所有節(jié)點(diǎn)的聯(lián)通情況。

• 每一個(gè) g[i] 也是一個(gè)并查集，記錄只添加 i—m 條邊時(shí)，所有節(jié)點(diǎn)的聯(lián)通情況。

• 對(duì)于每個(gè)詢問(wèn)只要把 f[l?1] 和 g[r+1] 合并至 H[] 中。

• 最后在 H[] 中判斷即可。

Code

#include<cstdio> #include<cstring> using namespace std; int n,m; struct data {int x,y; }a[10002]; int f[10002][501],g[10002][501],h[501]; inline int read() {int data=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data; }//讀入優(yōu)化 inline int getf(int k,int x) {if(f[k][x]==x) return x;return f[k][x]=getf(k,f[k][x]); }//F的查找 inline int getg(int k,int x) {if(g[k][x]==x) return x;return g[k][x]=getg(k,g[k][x]); }//G的查找 void init() {n=read();m=read();for(int i=1;i<=m;i++) a[i].x=read(),a[i].y=read();for(int i=1;i<=n;i++) f[0][i]=g[m+1][i]=i;//初值for(int i=1;i<=m;i++){memcpy(f[i],f[i-1],sizeof(f[i]));f[i][getf(i,a[i].x)]=getf(i,a[i].y);}//F的處理for(int i=m;i;i--){memcpy(g[i],g[i+1],sizeof(g[i]));g[i][getg(i,a[i].x)]=getg(i,a[i].y);}//G的處理 } inline int geth(int x) {if(h[x]==x) return x;return h[x]=geth(h[x]); }//H的查找 void work() {int k=read();while(k--){int l=read()-1,r=read()+1;memcpy(h,f[l],sizeof(h));for(int i=1;i<=n;i++) h[geth(h[i])]=geth(g[r][i]);//H的處理int ans=0;for(int i=1;i<=n;i++)if(h[i]==i) ans++;//H的判斷printf("%d\n",ans);} } int main() {freopen("connect.in","r",stdin);freopen("connect.out","w",stdout);init();work();return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 3453【NOIP2013中秋节模拟】连通块的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。