题解 AT2159 【連結 / Connectivity】

· · 题解

原题链接：

洛谷

AT

题意简述 &数据

这题在洛咕上的翻译是我交的。但是我要说明一点，题面里请把"或"改成"和"理解。（共有两处。如果已经更新过了，那么请忽略。我在讨论区里@管理了。。。）

思路

这题是STL的应用题，也是非常考思维的一个题目。首先，如果只有一种线路的话，就非常水了，并查集维护集合大小就珂以做了。

那么我们有两条线路，还要取交集，怎么办呢。。。

我们知道，并查集里面判定在同一个集合的方法是根据祖先判断。如果祖先相同，那就在一个集合里面，否则就不在。此时我们珂能会闪过一个念头：用一个数组（不妨叫R）记录两个线路的祖先。具体的说，设维护地铁线路的并查集叫D1，维护地面路径的并查集叫D2，此时R[i][j]表示：有多少个点满足在D1中的祖先是i，在D2中的祖先是j。那么，对于一个点u，它走两条线路都能到的点数量就是R[D1.find(i)][D2.find(i)]（其中find是查找祖先的函数）。记录这个数组的方法也很简单，就是对于每个点，R[D1.find(i)][D2.find(i)]++。

这个方法看起来很完美，珂是。。。空间？

BOOM！！！

如何优化？

map<pair<int,int>,int>。观察到，对于每个点，我们只会把这个数组的一个位置+1。所以说，真正有用的位置，顶多只有n个。那么我们用map<pair<int,int>,int>代替一个二维数组，就珂以省下很多空间。如果您不会这个操作，请看引用部分的说明。

说明： 我们还是设这个东西叫R。也就是我们定义map<pair<int,int>,int> R。 然后，对于(x,y)位置加上v的操作就是：R[make_pair(x,y)]+=v 对于位置(x,y)的值就是：R[make_pair(x,y)]

代码：

#include<bits/stdc++.h>
using namespace std;
namespace Flandle_Scarlet
{
    #define N 200100
    class DSU
    {
        public:
            int Father[N],Cnt[N];
            void Init()
            {
                for(int i=0;i<N;i++)
                {
                    Father[i]=i;
                    Cnt[i]=1;
                }
            }
            int Find(int x)
            {
                return (x==Father[x])?x:(Father[x]=Find(Father[x]));
            }
            void Merge(int x,int y)
            {
                int ax=Find(x),ay=Find(y);
                if (Cnt[ax]<Cnt[ay])
                {
                    Cnt[ay]+=Cnt[ax];
                    Father[ax]=ay;
                }
                else
                {
                    Cnt[ax]+=Cnt[ay];
                    Father[ay]=ax;
                }
            }
    }D1,D2;
    int n,k,l;
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Input()
    {
        R1(n),R1(k),R1(l);
        D1.Init();
        D2.Init();
        for(int i=1;i<=k;++i)
        {
            int a,b;
            R1(a),R1(b);
            D1.Merge(a,b);
        }
        for(int i=1;i<=l;++i)
        {
            int a,b;
            R1(a),R1(b);
            D2.Merge(a,b);
        }
    }
    #define pii pair<int,int>
    #define _1 first
    #define _2 second
    map<pii,int> rec;
    void Soviet()
    {
        for(int i=1;i<=n;++i)
        {
            int an1=D1.Find(i),an2=D2.Find(i);
            rec[make_pair(an1,an2)]++;
        }
        for(int i=1;i<=n;++i)
        {
            int an1=D1.Find(i),an2=D2.Find(i);
            printf("%d ",rec[make_pair(an1,an2)]);
        }
    }
    void IsMyWife()
    {
        if (0)
        {
            freopen("","r",stdin);
            freopen("","w",stdout);
        }
        Input();
        Soviet();
    }
};
int main()
{
    Flandle_Scarlet::IsMyWife();
    return 0;
}