并查集

感謝cyanigence-oi大佬(Orz)的題單

模板

并查集模板題

預處理過程：void pre()，賦值數組a

假設自己就是祖先，則用for循環，來儲存每個父親節點的值

void pre()
{
    for(int i=1;i<=n;i++) a[i]=i;
}

查詢過程：int find(int k)

用遞歸的形式一層一層的探索自己的祖先，根節點表示的就是祖先，判斷兩個人是不是同一個祖先，只要查詢各自的根節點是否相同即可

int find(int k)
{
    if(a[k]==k) return k;
    else return a[k]=find(a[k]);
}

合并過程：void merge(int u,int v)

void merge(int u,int v)
{
    a[find(u)]=find(v);
}

按秩合并

P1551 親戚

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll;
const int maxn = 2e5 + 10;
typedef long long ll;
ll n,m,p;
int a[maxn];
void pre()    //預處理
{
    for(ll i=1;i<=n;i++)
    {
        a[i]=i;
    }
}
ll find(ll k)    //查詢+路徑壓縮
{
    if(a[k]==k) return k;
    else return a[k]=find(a[k]);
}
void merge1(ll u,ll v)    //合并路徑
{
    a[find(u)]=find(v);
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&p);
    pre();
    ll x,y;
    for(ll i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        merge1(x,y);
    }
    for(ll i=1;i<=p;i++)
    {
        scanf("%lld%lld",&x,&y);
        if(find(x)==find(y))
            printf("Yes\n");
        else
            printf("No\n");
    }
}

P2814 家譜

用標準庫的map

#include <bits/stdc++.h>
using namespace std;
map<string,string>p;
string find(string x)
{
    if(p[x]==x) return x;
    else return p[x]=find(p[x]);
}
int main()
{
    string sss,ss;
    char c;
    while(1)
    {
        scanf("%c",&c);
        if(c=='$')
            break;
        else if(c=='#')
        {
            cin>>ss;
            if(p[ss]=="")
                p[ss]=ss;
        }
        else if(c=='?')
        {
            cin>>sss;
            cout<<sss<<" "<<find(sss)<<endl;
        }
        else if(c=='+')
        {
            cin>>sss;
            p[sss]=ss;
        }
    }
}

P1536 村村通

找查兩兩村是否聯通，即是否為同一個祖先，變量s作為記錄連通塊中的邊數，因為并不是每個村和其他的村莊都是聯通的，有可能存在鼓勵的村莊。

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll;
const ll maxn=2e5+10;;
ll n,m,a[maxn];
inline void pre()
{
    for(ll i=1; i<=n; i++)
    {
        a[i]=i;
    }
}
inline ll find(ll k)
{
    if(a[k]!=k) a[k]=find(a[k]);
    return a[k];

}
void merge(ll u,ll v)
{
    a[find(u)]=find(v);
}
int main()
{
    while(1)
    {
        ll f;
        scanf("%lld",&f);
        n=f;
        if(f==0) return 0;
        pre();
        scanf("%lld",&m);
        ll s=0;
        for(ll i=1; i<=m; i++)
        {
            ll x,y;
            scanf("%lld%lld",&x,&y);
            merge(x,y);
        }
        for(ll i=1; i<=n; i++)
        {
            if(a[i]==i)
            {
                s++;
            }
        }
        cout<<s-1<<endl;
    }
}

P1396 營救

創建結構體，存入u,v,w，對擁擠度w進行升序排序；

并查集，當查詢到s和t連通時，輸出當前的最大擁擠度，由于之前已經有過升序排序的操作，這時候的最大擁擠度是最小的。

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll;
const ll maxn=2e5+10;
struct node
{
    ll u,v,w;
}way[maxn];
inline bool cmp(node a,node b)
{
    return a.w<b.w;
}
ll n,m,s,t;
ll a[maxn];
void pre()
{
    for(ll i=0;i<maxn;i++)
    {
        a[i]=i;
    }
}
inline ll find(ll k)
{
    if(a[k]!=k)
    {
        a[k]=find(a[k]);
    }
    return a[k];
}
inline void merge(ll uu,ll vv)
{
    ll uuu=find(uu),vvv=find(vv);
    if(a[uuu]!=vvv)
        a[uuu]=vvv;
}
int main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    pre();
    for(ll i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&way[i].u,&way[i].v,&way[i].w);
    }
    sort(way+1,way+1+m,cmp);
    for(ll i=1;i<=m;i++)
    {
        merge(way[i].u,way[i].v);
        if(find(a[s])==find(a[t]))
        {
            printf("%lld\n",way[i].w);
            break;
        }
    }
}

P1621 集合

P4185 [USACO18JAN]MooTube

P1197 [JSOI2008]星球大戰

bzoj2054瘋狂的饅頭

P2294 [HNOI2005]狡猾的商人

P1892 [BOI2003]團伙

P1455 搭配購買

并查集+01背包

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, w;
ll a[100005], c[100005], d[100005],dp[100005];
void init()
{
    for (ll i = 1; i <= 100004; i++)
    {
        a[i] = i;
    }
}
ll find(ll k)
{
    if (a[k] == k)
    {
        return k;
    }
    else
    {
        return a[k] = find(a[k]);
    }
}
void merge(ll u, ll v)
{
    a[find(u)] = find(v);
}
int main()
{
    init();
    scanf("%lld %lld %lld", &n, &m, &w);
    for (ll i = 1; i <= n; i++)
    {
        scanf("%lld %lld", &c[i], &d[i]);
    }
    for (ll i = 1; i <= m; i++)
    {
        ll x, y;
        scanf("%lld %lld", &x, &y);
        merge(x, y);
    }
    ll s = 0;
    for (ll i = 1; i <= n; i++)
    {
        if (a[i] != i)
        {    
            d[find(i)] += d[i];
            d[i] = 0;
            c[find(i)] += c[i];
            c[i] = 0;
        }
    }
    for (ll i = 1; i <= n; i++)
    {
        for (ll j = w; j >= c[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - c[i]] + d[i]);
        }
    }
    printf("%lld\n", dp[w]);
}

帶權并查集

公司競爭

雖然題目給了2秒，但是也不可以一遍一遍的查詢，大佬何哥給了一種思路，即在每次認祖宗的時候，把兒子的勢力值加到父親的勢力值中，時間可以大大縮短，給1秒都夠

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, k;
ll a[100005], t[100005];
void init()
{
    for (ll i = 0; i < 100005; i++)
    {
        a[i] = i;
    }
}
ll find(ll k)
{
    if (a[k] == k)
    {
        return k;
    }
    else
    {
        return a[k] = find(a[k]);
    }
}
void merge(ll u, ll v)
{
    a[find(u)] = find(v);
}
int main()
{
    init();
    scanf("%lld %lld",&n,&m);
    for(ll i=1;i<=n;i++)
    {
        scanf(" %lld",t+i);
    }
    for(ll i=1;i<=m;i++)
    {
        ll f,x,y;
        scanf("%lld",&f);
        if(f==1)
        {
            scanf("%lld %lld",&x,&y);
            ll xx=find(x);
            ll yy=find(y);
            if(xx!=yy)
            {
                a[yy]=xx;
                t[xx]+=t[yy];
            }
        }
        else if(f==2)
        {
            scanf("%lld",&x);
            printf("%lld\n",t[find(x)]);
        }
    }
}

Interesting Computer Game 　　2020牛客暑期多校訓練營（第八場）

#include <bits/stdc++.h>
#define T int t ;cin >> t;while(t--)
using namespace std ;
typedef long long ll;
const int maxn = 2e5 + 10;
ll vis[maxn],a[maxn],b[maxn],c[maxn],pre[maxn];
//vis數組表示的是當前的節點是否被訪問過
//pre數組表示的是合并路徑
inline ll find(ll x)
{
    return (x==pre[x]) ? x:pre[x]=find(pre[x]);
}
inline void merge(ll u,ll v)
{
    ll x=find(u),y=find(v);
    if(x==y)
    {
        vis[x]=1;
        return;
    }
    pre[x]=y;//表示x，y的祖宗合并，即兩者為同一祖先
    if(vis[x])vis[y]=1;//該節點表示已被訪問
}
int main()
{
    ll total=0;//用于輸出Case情況的個數
    T
    {
        total++;
        ll n;
        ll tot=0;//tot表示存入數的個數
        scanf("%lld",&n);
        for(ll i=1; i<=n; i++)
        {
            scanf("%lld%lld",&a[i],&b[i]);
            c[++tot]=a[i];//c數組用于存放每個數字，方便接下去排序和去重，假設a和b的值完全不一樣，那么c數組的大小需要兩倍空間，即2e5+5
            c[++tot]=b[i];
        }
        for(ll i=0; i<=maxn; i++)//初始化操作
        {
            vis[i]=0;
            pre[i]=i;
        }
        sort(c+1,c+tot+1);//升序排序，便于接下來的去重
        int cnt=unique(c+1,c+tot+1)-(c+1);//去重，方便編號
        for(ll i=1; i<=n; i++)
        {
            a[i]=lower_bound(c+1,c+tot+1,a[i])-c;
//從數組的begin位置到end-1位置二分查找第一個大于或等于num的數字，
//找到返回該數字的地址，不存在則返回end。
//通過返回的地址減去起始地址begin,得到找到數字在數組中的下標，下標即樹的度數
            b[i]=lower_bound(c+1,c+tot+1,b[i])-c;
            merge(a[i],b[i]);//用下標代替實際數字，防止數組存不下
        }
        int ans=tot;
        for(ll i=1; i<=tot; i++)
        {
            if(pre[i]==i&&!vis[i])ans--;//根據《離散數學》相關知識，如果非連通塊則ans減一
        }
        cout<<"Case #"<<total<<": "<<ans<<endl;
    }
}

P3958 奶酪

被scy修改過的刪邊問題

貪心題

只要保證連通，即只要從樹根節點到達葉子節點，變成初級通路(每個點只經過一次，邊數=點數-1)，不必構成回路，結果等于原始總邊數(m)-初級通路(n-1)

#include <bits/stdc++.h>
using namespace std ;
int main()
{
    int a,b;
    cin>>a>>b;
    int bb=b;
    while(b--){int x;cin>>x>>x;}
    printf("%d\n",bb-a+1);
}

家族

查找連通塊的個數，如果a[i]==i，則s++，s變量統計的就是連通塊的個數。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll maxn=1e5+10;
ll a[maxn];
void pre()
{
    for(ll i=1;i<maxn;i++)
    {
        a[i]=i;
    }
}
inline ll find(ll k)
{
    if(a[k]==k)
    {
        return a[k];
    }
    else
    {
        return a[k]=find(a[k]);
    }
}
inline void merge(ll u,ll v)
{
    a[find(u)]=find(v);
}
ll n,m;
int main()
{
    scanf("%lld%lld",&n,&m);
    pre();
    ll x,y;
    for(ll i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        merge(x,y);
    }
    ll s=0;
    for(ll i=1;i<=n;i++)
    {
        if(a[i]==i)
            s++;
    }
    cout<<s<<endl;
}

posted @ 2020-08-02 16:35 Drophair 閱讀(186) 評論(0) 收藏舉報

刷新頁面返回頂部

Drophair

GitHub：https://github.com/drophair

并查集

并查集模板題

P1551 親戚

P2814 家譜

P1536 村村通

P1396 營救

P1621 集合

P4185 [USACO18JAN]MooTube

P1197 [JSOI2008]星球大戰

bzoj2054瘋狂的饅頭

P2294 [HNOI2005]狡猾的商人

P1892 [BOI2003]團伙

P1455 搭配購買

公司競爭

P3958 奶酪

被scy修改過的刪邊問題

家族

公告

GitHub：https://github.com/drophair

并查集 模板題

公告

并查集模板題