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

牛客小白月赛25 C白魔法师 —— bfs & 并查集

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

题目描述:题目链接
牛客小白月赛25 C白魔法师 —— bfs & 并查集
题意分析:
n个节点 n-1条边,非常明显的树形结构(题目中就有说 ),因此不需要考虑环的情况。
树上有两种颜色,一种是白色一种是黑色,我们可以推断出这题应该是考虑连通块的大小,那么考虑两种思路,一种是bfs,一种是并查集。

1.bfs
我们可以用siz来记录这个连通块的大小,vis来记录这个点是否被访问到,sd记录每个点属于哪个连通块,因此利用bfs深搜的性质可得到所有连通块的大小。然后我们再逐个点处理,如果这个点是B,那么我们考虑如果将这个点染成白色之后的连通块大小,下面贴上代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, cc, k, Maxsize;
int vis[N], sd[N], siz[N];
vector<int> g[N];
char ss[N];
void bfs(int s) {
    queue<int> q;
    q.push(s);
    vis[s] = 1;
    siz[k]++;
    sd[s] = k;
    while (q.size()) {
        int u = q.front();
        q.pop();
 
        for (auto v : g[u]) {
            if (!vis[v] && ss[v] == 'W') {
                vis[v] = 1;
                sd[v] = k;
                siz[k]++;
                q.push(v);
            }
        }
    }
    Maxsize = max(Maxsize, siz[k]);
}
 
int main() {
    cin >> n;
    cin >> ss + 1;
    for (int i = 1; i <= n; i++) if (ss[i] == 'B') cc++;
 
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
 
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && ss[i] == 'W') {
            k++;
            bfs(i);
        }
    }
    int Max = 0;
    for (int i = 1; i <= n; i++) {
        int ans = 0;
        if (ss[i] == 'B') {
            for (auto v : g[i]) {
                ans += siz[sd[v]];
            }
        }
        Max = max(Max, ans + 1);
    }
    if (!cc) cout << Maxsize;
    else cout << Max;
}

2.并查集
同样我们可以利用并查集的性质将点与点联系起来,类似于kruskal算法中的应用。然后同理利用siz记录每个连通块的大小,最后对每个B节点处理过程如上。
下面给出代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int fa[N], cc;
char ss[N];
int siz[N], n, Maxsize;
vector<int> g[N];
int find(int x) {
	if (x == fa[x]) return x;
	else return fa[x] = find(fa[x]);
}

void combine(int x, int y) {
	int t1 = find(x), t2 = find(y);
	if (t1 != t2) {
		if (siz[t1] >= siz[t2]) {
			fa[t2] = t1;
			siz[t1] += siz[t2];
		}
		else {
			fa[t1] = t2;
			siz[t2] += siz[t1];
		}
	}
}

int main() {
	cin >> n;
	cin >> ss + 1;
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
		if (ss[i] == 'W') siz[i] = 1;
		else cc++;
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
		if (ss[x] == ss[y] && ss[x] == 'W') combine(x, y);
	}

	int Max = 0;
	for (int i = 1; i <= n; i++) {
		int ans = 0;
		if (ss[i] == 'B') {
			for (auto v : g[i]) {
				if (ss[v] == 'W') ans += siz[find(v)];
			}
		}
		Max = max(Max, ans + 1);
	}
	if (!cc) cout << n;
	else cout << Max;

}

并查集:
牛客小白月赛25 C白魔法师 —— bfs & 并查集
bfs:
牛客小白月赛25 C白魔法师 —— bfs & 并查集
最后对比发现并查集在时间复杂度上确实优于bfs。