【問題描述】

在遙遠的 S 星系中一共有 N 個星球,編號為 1…N。其中的一些星球決定組成聯(lián)盟,
以方便相互間的交流。
但是,組成聯(lián)盟的首要條件就是交通條件。初始時,在這 N 個星球間有 M 條太空
隧道。每條太空隧道連接兩個星球,使得它們能夠相互到達。若兩個星球屬于同一個聯(lián)
盟,則必須存在一條環(huán)形線路經(jīng)過這兩個星球,即兩個星球間存在兩條沒有公共隧道的
路徑。
為了壯大聯(lián)盟的隊伍,這些星球將建設 P 條新的太空隧道。這 P 條新隧道將按順序
依次建成。一條新軌道建成后,可能會使一些星球屬于同一個聯(lián)盟。你的任務是計算出,
在一條新隧道建設完畢后,判斷這條新軌道連接的兩個星球是否屬于同一個聯(lián)盟,如果
屬于同一個聯(lián)盟就計算出這個聯(lián)盟中有多少個星球。

【輸入格式】

第 1 行三個整數(shù) N,M 和 P,分別表示總星球數(shù),初始時太空隧道的數(shù)目和即將建
設的軌道數(shù)目。
第 2 至第 M+1 行,每行兩個整數(shù),表示初始時的每條太空隧道連接的兩個星球編
號。
第 M+2 行至第 M+P+1 行,每行兩個整數(shù),表示新建的太空隧道連接的兩個星球編
號。這些太空隧道按照輸入的順序依次建成。

【輸出格式】

輸出共 P 行。如果這條新的太空隧道連接的兩個星球屬于同一個聯(lián)盟,就輸出一個
整數(shù),表示這兩個星球所在聯(lián)盟的星球數(shù)。如果這條新的太空隧道連接的兩個星球不屬
于同一個聯(lián)盟,就輸出”No”(不含引號)。

【樣例 1】

alliance.in
3 2 1
1 2
1 3
2 3
alliance.out
3

【樣例 2】

alliance.in
5 3 4
1 2
4 3
4 5
2 3
1 3
4 5
2 4
alliance.out
No
3
2
5

【數(shù)據(jù)范圍】
對于 10%的數(shù)據(jù)有 1≤N,M,P≤100;
對于 40%的數(shù)據(jù)有 1≤N,M,P≤2000;
對于 100%的數(shù)據(jù)有 1≤N,M,P≤200000。

【題解】

算法一:暴力枚舉

對于每一個詢問我們可以枚舉每一條邊,去掉后判斷點對之間的連通性即可。
時間復雜度:O(N(M+P)2)
期望得分:10 分

算法二:樸素的強連通分量

很明顯對于每一個詢問,我們可以計算當前圖的強連通分量,加以判斷。使用時間復雜度均為 O(N) kosaraju 或 tarjan 算法。
時間復雜度:O(N(M+P))
期望得分:40 分

算法三:模型的轉換與多種圖論算法的綜合運用

每一次都計算強連通分量顯然不合適,這樣會連帶計算出很多我們不需要的連通分量,我們要做的就是對新加的邊的兩個端點進行分析。很明顯,如果這兩個點已經(jīng)處于同一個強連通分量中,就不必改變,如果這兩個點不在同一個強連通分量中,可能有兩種情況:

1、這條邊使得那兩個點處于同一強連通分量中。
2、這條邊使得兩個點聯(lián)通,即當前通的一個橋。

對于第二種情況,可以預先處理,然而對于第一種情況又該如何處理呢?很明顯,如果這條邊使得原本不在同一強連通分量的兩個點處在了統(tǒng)一的強連通分量,則在添加這條邊之前這兩個點之間有且僅有唯一一條路徑相連。這讓我們想起了一種特殊的圖——樹!樹中任意的兩個節(jié)點之間有且僅有唯一一條路徑相連。那么如何將原圖轉化為一棵樹呢?

實際上我們可以將上面所說的情況 2 的邊看作為一條樹邊,很明顯一個包含N 個節(jié)點的圖最多含有 N-1 個橋。將這些橋預先計算出來后,我們可以構造一個樹(或森林)。對于一棵樹,若樹上的兩個點不是父子關系,而它們之間新添加了一條邊,那么這條邊可能形成新的強連通分量,由樹的性質,添加過新的邊之后,這兩個點和這兩個點所在路徑上所有的點一定處于一個強連通分量之中。對于給定的兩個節(jié)點,我們可以先找到其最近公共祖先(lca),在將 lca 到這兩個點的路徑上所有的點合并為同一個強連通分量。這里可以用并查集維護。初始時每個節(jié)點指向自己,在合并時,將指針指向所合并的 lca。如上圖,當我們新添加紅色標出的那條邊時,可以將所有綠色的點指向 lca,也就是藍色的點。在維護并查集時,要注意并查集元素大小的累加。接下來的問題就是如何找到兩個點的最近公共祖先呢?最近公共祖先有一個特點:它在樹中的高度 H 不大于所要查詢的那兩個節(jié)點在樹中的高度。我們可以迭代完成查詢 lca 的過程。例如:給定兩個點 X,Y,我們得到這兩個點在樹中的高度,接下來如果 Hx>=Hy 我們就將 X 替換為它的父親(這里的父親指縮點后的父親),否則就將 Y 替換為它的父親,直到 X=Y 為止。這期間,我們可以順便完成并查集的合并操作。

顯然,一開始我們還需進行對每個節(jié)點 H 的計算,這里推薦用 BFS(DFS
可能會爆棧)更為合適。需要注意的是,給定的圖未必聯(lián)通,所以構成的可能不
是樹而是森林。

下面讓我們總結這個算法的流程:
第一步:依據(jù)輸入數(shù)據(jù)構造出樹或森林,這里可以用強連通分量找橋也可以選用并查集。
第二步:BFS 計算出每個節(jié)點 H 的大小。
第三步:依次處理新加的 P 條邊,維護并查集完成 lca 查詢及縮點操作。
時間復雜度:O(N+M+P)
期望得分:100 分。

涉及內容: 1.圖與樹的轉化
2.并查集、強連通分量算法
3.寬度優(yōu)先搜索
4.數(shù)據(jù)的預處理與再處理。

#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> #define ll long long #define re register #define il inline #define fp(i,a,b) for(re int i=a;i<=b;i++) #define fq(i,a,b) for(re int i=a;i>=b;i--) using namespace std; const int MAX=200005; struct Edge {int to,next; }a[MAX<<1]; struct solve {int x,y; }put[MAX],que[MAX]; int size[MAX],deep[MAX],f[MAX]; int head[MAX],tot,Fa[MAX]; int n,m,q,cnt,qcnt,num[MAX]; il void add(int u,int v) {a[++tot]=(Edge){v,head[u]};head[u]=tot;a[++tot]=(Edge){u,head[v]};head[v]=tot; } il int find(int x) {return (f[x]==x)?f[x]:(f[x]=find(f[x])); } il void dfs(int u,int fa) {deep[u]=deep[fa]+1;for(int i=head[u];i;i=a[i].next){int v=a[i].to;if(v!=fa) Fa[a[i].to]=u,dfs(v,u);} } void Union(int u,int v) {while(u!=v){if(deep[u]<deep[v]) swap(u,v);int x=find(u),y=find(Fa[u]);//最后問題出在這里，Fa[u]打成了f[u]fif(x!=y) {f[x]=y,size[y]+=size[x];}u=y;} } il int gi() { re int x=0;re short int t=1;re char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-') t=-1,ch=getchar();while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*t; } int main() {freopen("alliance.in","r",stdin);freopen("alliance.out","w",stdout);n=gi(),m=gi(),q=gi();fp(i,1,n) f[i]=i;fp(i,1,m){int u=gi(),v=gi();int x=find(u),y=find(v);if(x!=y) f[y]=x,add(u,v);else put[++cnt].x=u,put[cnt].y=v;}fp(i,1,q){int u=gi(),v=gi();int x=find(u),y=find(v);if(x!=y) f[y]=x,add(u,v);else que[++qcnt].x=u,que[qcnt].y=v,num[i]=qcnt;}fp(i,2,n){int x=find(i),y=find(1);if(x!=y) add(i,1),f[x]=y;}fp(i,1,n) f[i]=i,size[i]=1;dfs(1,0);fp(i,1,cnt)Union(put[i].x,put[i].y);fp(i,1,q)if(!num[i]) printf("No\n");else{Union(que[num[i]].x,que[num[i]].y);printf("%d\n",size[find(que[num[i]].x)]);}fclose(stdin);fclose(stdout);return 0; }

轉載于:https://www.cnblogs.com/yanshannan/p/7413155.html

總結

以上是生活随笔為你收集整理的[置顶]星球联盟的全部內容，希望文章能夠幫你解決所遇到的問題。

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