【题解】星球大战&银河英雄传说

别急别急,先放完战歌再开战

不懂并查集者勿入,因为。。。我懒得再写一遍并查集了。

相似点

1.都用并查集可以完成。
2.都是并查集的变形。
3.本蒟蒻不看题解都做不出来

星球大战

解题思路

在我请教hry大佬的时候他立刻回复:“这题你还做不了,这题是割点的题。”(我太弱了)
看过题解的我说:“这道题是并查集好吗?”
他突然回过神来:“哦对反着扫似乎用并查集能过QAQ”

大佬的思维跳跃性就是这么快。

其实这道题最简单的做法是并查集。但是割点也是能做的 (只是我不知道怎么做)

下面开始正题
主要思路就是先找到星球全部摧毁的状态,然后在倒过来得出星球被摧毁以前的状态。

我们先把星球全部毁灭光,并用broke数组记录下被摧毁的星球。于是就开始了我们的类初始化:

for(int i=0;i<m;i++){
    if(!broke[xx[i]]&&!broke[yy[i]]){//xx[i]和yy[i]是两个相连的点。
        unite(xx[i],yy[i]);//unite就是并查集里面的合并操作。
    }
}

我们再重建(找到未摧毁的状态)。但是大佬们会发现如果按照普通的每恢复一个星球求一遍连通块的个数,需要O(nm)的时间复杂度,我们无法接受。于是就立刻得出可以先求出毁灭光的时候的联通块个数,然后如果两个不同的连通块合并了,就将连通块个数减少1。(注意,这里被毁灭的星球不算连通块)

代码

//求出星球被毁灭光时的连通块个数。
for(int i=0;i<n;i++){
    if(head[i]==i){
        ans[k]++;
    }
}
//时光倒流。。。
for(int i=k-1;i>=0;i--){
    ans[i]=ans[i+1]+1;//被摧毁的星球少了一个,于是连通块就多了一个。
    for(vector<int>::iterator it=G[killed[i]].begin();it<G[killed[i]].end();it++){//这里使用vector存图。
        if(find(killed[i])!=find(*it)&&!broke[*it]){//之所以要!broke[*it]是因为如果另一个点还是在被摧毁的状态下,就无法连接。
            unite(killed[i],*it);
            ans[i]--;
        }
    }
    broke[killed[i]]=0;
}

最后贴完整代码

#include<bits/stdc++.h>
using namespace std;
int xx[200005],yy[200005];
bool broke[400005];
vector<int> G[400005];
int head[400005];
int ans[400005];
int killed[400005];//killed[i]和broke[i]的不同点是killed[i]记录顺序,broke[i]记录状态
int find(int a){
    if(a==head[a]){
        return a;
    }
    return head[a]=find(head[a]);
}
void unite(int a,int b){
    int fa=find(a);
    int fb=find(b);
    if(fa!=fb){
        head[fa]=fb;
    }
    return ;
}
int main(){
    for(int i=0;i<400005;i++){
        head[i]=i;
    } 
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>xx[i]>>yy[i];
        G[xx[i]].push_back(yy[i]);
        G[yy[i]].push_back(xx[i]);
    }
    int k,tmp;
    cin>>k;
    for(int i=0;i<k;i++){
        cin>>killed[i];
        broke[killed[i]]=1;
    }
    for(int i=0;i<m;i++){
        if(!broke[xx[i]]&&!broke[yy[i]]){
            unite(xx[i],yy[i]);
        }
    }
    
    for(int i=0;i<n;i++){
        if(head[i]==i){
            ans[k]++;
        }
    }
    ans[k]-=k;
    for(int i=k-1;i>=0;i--){
        ans[i]=ans[i+1]+1;
        for(vector<int>::iterator it=G[killed[i]].begin();it<G[killed[i]].end();it++){
            if(find(killed[i])!=find(*it)&&!broke[*it]){
                unite(killed[i],*it);
                ans[i]--;
            }
        }
        broke[killed[i]]=0;
    }
    for(int i=0;i<=k;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}

银河英雄传说

解题思路

做这道题的时候在最后的步骤上想了半天。。。见鬼。。。

这道题判断是否在同一列上是pj-的难度,然后突然要求中间的战舰数~

首先当然是要判断是否在同一列上。用并查集随便一套即可。下面开始正文:如何求中间的战舰数

既然要求中间的战舰数,那我们必须得知道每个战舰在所在集合的位置在哪里。我们用dis[i]表示i到i所在的集合的根节点的距离。

而为了合并两批战舰,我们还要知道每一列的战舰个数,以便之后合并时直接求出加入战舰的dis。

//初始化
for(int i=0;i<30005;i++){
    head[i]=i;
    dis[i]=0;
    big[i]=1;//big[i]就是第i列战舰的数量~
}
//合并两列战舰
int fx=find(x);
int fy=find(y);
//如果想改成dis[fx]=big[fy]也无妨
dis[fx]+=big[fy];//将x的根节点加入到y中,x的根节点离y的根节点的距离为y.size()。
big[fy]+=big[fx];//y的集合既然包括了x的集合,那么战舰数肯定要增加。
big[fx]=0;//x都走了,那么数量就变成了0。
if(fx!=fy){
    head[fx]=fy;
}

划重点:find()函数该怎么写

int find(int x){
    if(x==head[x]){
        return x;
    }
    int acst=find(head[x]);//这里再递归后还要操作,所以不能直接return head[x]=find(head[x])
    dis[x]+=dis[head[x]];//最诡异的地方来了。
//这里其实head[x]是之前未更新的x的根节点,当有新的根节点加入时,x离新根节点的距离就是 x离原根节点的距离+原根节点离新根节点的距离。
    return head[x]=acst;
}

萌新求助:为什么我一直觉得没有遍历到所有x?大佬们可以在评论区答复,感谢!

代码

#include<bits/stdc++.h>
using namespace std;
int head[30005],dis[30005];
int big[30005];
int find(int x){
    if(x==head[x]){
        return x;
    }
    int acst=find(head[x]);
    dis[x]+=dis[head[x]];
    return head[x]=acst;
}
void unite(int x,int y){
    int fx=find(x);
    int fy=find(y);
    dis[fx]=big[fy];
    big[fy]+=big[fx];
    big[fx]=0;
    if(fx!=fy){
        head[fx]=fy;
    }
}
int main(){
    for(int i=0;i<30005;i++){
        head[i]=i;
        dis[i]=0;
        big[i]=1;
    }
    int n;
    cin>>n;
    char op;
    int x,y;
    for(int i=0;i<n;i++){
        cin>>op>>x>>y;
        if(op=='M'){
            unite(x,y);
        }else{
            if(find(x)==find(y)){
                cout<<abs(dis[x]-dis[y])-1<<endl;
            }else{
                cout<<"-1"<<endl;
            }
        }
    }
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/572/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者