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

白魔法师--图的连通块问题(牛客小白月赛25)

程序员文章站 2022-06-08 16:44:51
...

链接:题目链接
来源:牛客网

白魔法师

时间限制:C/C++ 1秒,其他语言2秒

空间限制:C/C++ 262144K,其他语言524288K

64bit IO Format: %lld

题目描述

你是一个白魔法师。
现在你拿到了一棵树,树上有 个点,每个点被染成了黑色或白色。
你可以释放一次魔法,将某个点染成白色。(该点不一定是黑色点,也可以是白色点)
现在释放魔法后要保证最大的白色点连通块尽可能大。请求出最大白色连通块的大小。
注:所谓白色连通块,指这颗树的某个连通子图,上面的点全部是白色。

输入描述:
第一行输入一个正整数 ,代表树的顶点数量。
第二行输入一个长度为 的、仅由’W’和’B’组成的字符串,第 个点为’W’代表该点为白色,'B’代表该点为黑色。
接下来的 行,每行输入两个正整数 和 ,代表 点和 点有一条边连接。
输出描述:
一个正整数,代表施放魔法后,最大的白色连通块的大小。
输入:

4
WBBW
1 2
2 3
3 4

输出:

2

思路:
图的连通块问题,找出各个节点的白色连通块大小,最后再处理一下
白魔法师--图的连通块问题(牛客小白月赛25)
资料:图的连通块问题
代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll N=1e5+5;
int n,tot,vis[N],num[N];
char s[N]; 
vector<int> g[N];
void dfs(int u)//根节点 
{
 vis[u]=tot;//标记每个点属于那个连通块 
 ++num[tot];//记录有多少个白子节点 
 for(int i=0;i<g[u].size();++i)
 {
  int to=g[u][i];
  if(vis[to]==0&&s[to]=='W')//走没走过且为白色的点 
  {
   dfs(to);
  }
 } 
}
int main()
{
 cin>>n>>s+1;
 ll x,y;
 for(int i=1;i<n;i++)
 {
  cin>>x>>y;
  g[x].push_back(y);
  g[y].push_back(x);//加入 ,记录有边的节点 
 }
 for(int i=1;i<=n;i++)
 {
  if(vis[i]==0&&s[i]=='W')//找没有遍历过的节点,划分连通块 
  {
   tot++;//标记联通块的个数 
   dfs(i);
  }
 }
 int ans=0;
 for(int i=1;i<=n;i++)
 {
  if(s[i]=='W')
  {
   ans=max(ans,num[vis[i]]);
  }
  else 
  {
   int v=1;//因为会是魔法改变一次节点颜色 
   for(int j=0;j<g[i].size();j++)
   {
    int to=g[i][j];
    if(s[to]=='W')
    {
     v+=num[vis[to]];
    }
   }
   ans=max(ans,v);
  }
 }
 cout<<ans<<endl;
    return 0;
}
相关标签: 数据结构