P6279 [USACO20OPEN]Favorite Colors G 题解

· · 题解

看到题解里有些地方没有详细讲到，这里来补一发。

题意简化

（这道题我读了好久才看懂…）

每个奶牛都有自己喜欢的颜色。其中，如果奶牛 A 和奶牛 B 都仰慕一头喜欢颜色 c 的奶牛，那么它们喜欢的颜色需要相同。

在以上条件下，找到一种奶牛喜欢颜色的分配方案，可以让奶牛喜欢的颜色尽量不相同，输出字典序最小的答案。

算法分析

根据【样例分析】的启发，我们可以考虑连一幅图：

然后我们首先可以发现，同一个点所连接的所有点的颜色都必须相同。

比如 3 号节点连接了 5,4 号节点，那么按照要求，4,5 号奶牛的颜色必须都是一样的。因此，我们可以考虑将它们合并。

这样做的目的是保证每一个节点中所含的奶牛都必须是同样的一个颜色，这样，当结束时，有多少个点集，就至少有多少个颜色集合。

于是我们合并 4,5 号节点：

以此类推，不断合并成：

到这一步的时候，可以发现，每一个点最多向外连一个点，也就是说，每个点的出度 <2。因此，不再有新的点一定要变成同一种颜色了，所以结束合并过程，1,4,5 一种颜色，3,7,9 一种颜色，2,6,8 一种颜色。

算法实现

那么，合并的过程怎么实现呢？

我们可以用类似并查集的方式来做。

对于每一个点，我们都可以将其想象成一棵有根树（只是思维上的，不是实现），并且深度 ≤2（根节点深度为 1）。当要合并两个点的时候，我们只需要将一个节点的根节点和其子节点都加到另一棵树根节点下就可以了。

举个例子，比如我们要把左边的节点合并到右边的节点：

那么新的节点就会变成：

这便是合并方法了。

启发式合并

然而

掐指一算，发现时间复杂度极限可以达到 O(n^2)，应该是过不了的。

于是考虑一种玄学的操作——启发式合并！

其实就是当我们要合并两个节点的时候，考虑哪个节点所包含的奶牛数少，就合并过去哪个节点。

比如上文的例子：

我们就应该将右边的节点并到左边的节点里，这样便可以更快进行合并。

没有了，简单吧

这个时候可能有人就有疑惑了，这不只是一种卡常的手段吗？为什么就能通过这道题呢？

这个算法最令人惊叹的就是，它的时间复杂度是严格 O(nlogn)！

感兴趣的同学可以看以下的证明（不一定要掌握）：

考虑计算每一个奶牛最多会被合并几次（如果每一头奶牛合并次数都小于等于 logn，那么总时间复杂度就 是 O(nlogn)）。如果 h 号奶牛要从大小为 x 的节点并入大小为 y 的节点，那么必有 x≥y，则合并后节点的大小 x+y≥2y。也就是说，一头奶牛所在的节点进过一次合并之后，奶牛所在节点的大小一定会至少乘 2，因此，一头奶牛最多被合并 logn 次。

证毕。

很神奇吧

代码实现

以上只是算法分析，代码上还是有很多细节的。看注释吧：


#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=200002;
inline int read()
{
    register int x=0;
    register char c=getchar();
    for(;!(c>='0'&&c<='9');c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+c-'0';
    return x;
}
int n,m;
vector<int>v[maxn];//存边
vector<int>son[maxn];
//son[i]:若i号奶牛是其所在节点的（那棵树的）根节点，
//那么存储所在节点的（那棵树的）所有节点
queue<int>q;
int fa[maxn];//fa[i]:i号奶牛所在节点的（那棵树的）根节点
int Vis[maxn],ans[maxn];
void hb(int x,int y)
{
    x=fa[x],y=fa[y];//对根节点进行操作
    if(son[x].size()<son[y].size())//启发式合并核心代码
        x^=y,y^=x,x^=y;
    for(register int i=0;i<v[y].size();i++)
        v[x].pb(v[y][i]);//合并
    for(register int i=0;i<son[y].size();i++)
        fa[son[y][i]]=x,son[x].pb(son[y][i]);//合并
    if(v[x].size()>1)
      //如果仰慕的奶牛超过一头，需要合并，入队列 
        q.push(x);
}

int main()
{
    register int x,y,t,ru;
    n=read(),m=read();
    for(register int i=1;i<=m;i++)
        x=read(),y=read(),v[x].pb(y);
    for(register int i=1;i<=n;i++)
    {
        fa[i]=i;//一开始每个奶牛所在节点的根节点都是它自己
        if(v[i].size()>1)
     //如果有超过一头奶牛仰慕当前奶牛，那么需要合并，加入队列
        q.push(i);
        son[i].pb(i);
      //一开始每个奶牛都是所在节点的根节点节点，且节点中必定有这头奶牛（废话）
    }       
    while(!q.empty())
    {
        t=q.front(),q.pop();
        while(v[t].size()>1)
        {
            ru=v[t][1],x=v[t][0],v[t].erase(v[t].begin());
            if(fa[ru]!=fa[x])
         //如果不是同一节点中的奶牛再合并，防止计算重复
                hb(ru,x);
        }
    }
    register int col=0;
    for(register int i=1;i<=n;i++)
    {
        if(Vis[fa[i]]==0)
            Vis[fa[i]]=++col;
        cout<<Vis[fa[i]]<<endl;
    }
    return 0;
}