欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客小白月赛25 C-白魔法师 ( 图论 + 并查集 )

程序员文章站 2022-03-13 17:08:41
...

题目链接
牛客小白月赛25 C-白魔法师 ( 图论 + 并查集 )
解题报告:
思路:如果将一个黑色点染成白色,那么将得到一个白色连通块,这个连通块由和这个黑色点连结的所有白色连通块组成。
如果将一个白色点染成白色,那么不会有任何变化。
所以我们可以先并查集预处理一下,把所有白色连通块的大小求出来,并把所有白色点对应的连通块表示一下。连通块的大小可以dfs或者统计并查集根的孩子总数得出
然后统计所有黑色点的邻点连通块大小即可。要注意特判全部是白色点的情况

#define first f
#define second s
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define sl(p) strlen(p)
#define SZ(p) p.size()
#include <bits/stdc++.h>
#define lb lower_bound
#define ub upper_bound
#define mem(a,b) memset(a,b,sizeof(a))
#define fast_cin  ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
using namespace std;
const ll MOD=1e9+7;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
const long double eps=1e-8;

int sz[maxn],sm[maxn],f[maxn];
vector<int>g[maxn];
char p[maxn];
int getfind(int x)
{
    return f[x]==x?x:f[x]=getfind(f[x]);
}
void Union(int x,int y)
{
    x=getfind(x),y=getfind(y);
    if(x!=y){
        if(sm[x]<sm[y]) f[x]=y,sm[y]+=sm[x];
        else f[y]=x,sm[x]+=sm[y];
    }
}
int main()
{
    int n,u,v;
    scanf("%d%s",&n,p+1);
    for(int i=1;i<=n;i++) sm[i]=1,f[i]=i;
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        g[u].pb(v);g[v].pb(u);
        if(p[u]=='W'&&p[v]=='W') Union(v,u);
    }
    for(int i=1;i<=n;i++) sz[i]=sm[getfind(i)];
    int ans=-1;
    for(int i=1;i<=n;i++){
        if(p[i]=='B'){
            int res=1;
            for(int j=0;j<SZ(g[i]);j++){
                if(p[g[i][j]]=='W') res+=sz[g[i][j]];
            }
            ans=max(ans,res);
        }
    }
    printf("%d\n",ans==-1?n:ans);
    return 0;
}