白魔法师--图的连通块问题(牛客小白月赛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
思路:
图的连通块问题,找出各个节点的白色连通块大小,最后再处理一下
资料:图的连通块问题
代码:
#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;
}