實作并查集和DFS的一些有趣方法

文章目錄

• • 一、實作并查集的簡潔寫法
  • 二、關于一些DFS和DP的使用
  • • question1：
    • question2:關于多參數DFS的使用
    • question3:記憶化方法實作

一、實作并查集的簡潔寫法

大佬的有趣解釋

int lead(int x)//
{
    if(leader[x]==x) return x;
    else return leader[x]=lead(leader[x]); //把路徑上所有點都糾正
}
int link(int x,int y)
{
   if(leader[x]!=leader[y])
   {
        leader[lead(x)]=lead(y);
   }
}
           

leader[]表示直屬上級

link()實作了兩個互不相關組的連接配接，把x的root一起并入y的子結點中

note：return leader[x]=lead(leader[x])要用遞歸的思想去了解，先改變上級與root的link再遞歸回來改變自己。

二、關于一些DFS和DP的使用

Despite the fact that DFS has certain templates，we should not let them limit our thoughts，because we create DFS，（it is easy now to find people using DFS but it gets much harder to find a skilled DFS master.）Below are some examples.(haha，just a English Beginner trying to write something)

question1：

戳我跳轉

對于dfs，經常使用遞歸方式實作，正向有時候很好用

從上往下依次推出金字塔各個位置上的最大值，最後比較

#include<cstdio>
int n,a[1002],i,j,ans,p;
int max(int &x,int &y){return x>y?x:y;}
int main(){
    scanf("%d",&n);
        for(i=n;i;i--)
                for(j=i;j<=n;j++)
                        scanf("%d",&p),a[j]=max(a[j],a[j+1])+p;
        for(i=1;i<=n;i++)
        ans=max(ans,a[i]);
        printf("%d",ans);
        return 0;
}
           

question2:關于多參數DFS的使用

戳我跳轉

DFS在于實作層層遞歸，是以需要把重要參數層層傳遞。

下面這道題在進行層層深入時使用了

stp：走的步數 （用于還原路徑）

sum：挖礦總數

x:要走的位置

#include<iostream>
#include<cstdio>
using namespace std;
bool v[30];//是否通路過
int bomb[30];//地雷數目
int path[30],ans[30],cnt;//path記錄路徑
int ac[30][30];//檢視是否有通路
int n;
int maxx;//記錄最大地雷數目
bool check(int x)
{
    for(int i=1;i<=n;i++){
        if(ac[x][i]&&!v[i]) return false;
    }
}
int dfs(int x,int stp,int sum)//走步數
{
    if(check(x))
    {
        if(maxx<sum)
        {
            maxx=sum;
            cnt=stp;
            for(int i=1;i<=stp;i++){
                ans[i]=path[i];
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(ac[x][i]&&!v[i]){
            v[i]=1;//标記走過
            path[stp+1]=i;//記錄路徑
            dfs(i,stp+1,sum+bomb[i]);
            v[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>bomb[i];
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++) 
            cin>>ac[i][j];
    for(int i=1;i<=n;i++){
        v[i]=1;
        path[1]=i;
        dfs(i,1,bomb[i]);
        v[i]=0;
    }
    for(int i=1;i<=n;i++){
        v[i]=1;
        path[1]=i;
        dfs(i,1,bomb[i]);
        v[i]=0;
    }
    for(int i=1;i<=cnt;i++)
    cout<<ans[i]<<' ';
    cout<<endl<<maxx;
    return 0;
}
           

question3:記憶化方法實作

戳我

#include<iostream>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m,a[201][201],s[201][201],ans;
bool use[201][201];
int dfs(int x,int y)
{
    if(s[x][y]) return s[x][y];
    s[x][y]=1;
    for(int i=0;i<4;i++){
        int xx=dx[i]+x;
        int yy=dy[i]+y;
        if(xx>0&&yy>0&&xx<=n&&yy<=m&&a[x][y]>a[xx][yy]){
            dfs(xx,yy);
            s[x][y]=max(s[x][y],s[xx][yy]+1);
        }
    }
    return s[x][y];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++)
           ans=max(ans,dfs(i,j));
    cout<<ans;
    return 0;     
}
           

實作了每走一條路标記一條路。有點最優子結構的dp的意思了