思路：并查集

给定一个无向图，有些节点是白色，有些节点是红色。求将第$i$个节点染红后，有多少个红色连通块。

红色节点染红，显然红色连通块的数目不变。

将白色节点染红，则要取决于与该染红节点相邻的节点有多少已经是红色的。而这些已经是红色的节点有可能已经位于同一个连通块中了，因此我们需要使用并查集来判断它们是否处于同一个集合。

最开始，通过某一个未被标记的红色节点开始遍历，将其所能到达的所有红色节点划分到该集合中，然后标记。重复上述过程，直到所有红色节点都被划分进集合中。此时可以求到集合总数为$res$，也就是最开始的答案或者说将红色节点染红的答案。

然后开始求取答案。

由于有了并查集，当我们将一个白色节点染红时，可以遍历所有与相邻的节点，计算有多少个集合，假设为$x$，那么最终的答案即为$res-x+1$

代码

C++

AC

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 1e5 + 10;
int n, m;
char c[maxn];
int head[maxn], ver[maxn << 1], Next[maxn << 1], tot = 1;
int fa[maxn];
bool book[maxn];

// 添加一条边
void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}

// 查找父节点
int find(int x) {
    return fa[x] = (x == fa[x] ? x : find(fa[x]));
}

// 合并两个集合
void merge(int x, int y) {
    int fax = find(x);
    int fay = find(y);
    if (fax != fay) fa[fax] = fay;
}

// 深度优先搜索，建立红色连通分量
void dfs0(int x) {
    book[x] = true;
    for (int i = head[x], y; i; i = Next[i]) {
        y = ver[i];
        if (c[y] == 'R' && !book[y]) {
            merge(x, y);
            dfs0(y);
        }
    }
}

// 计算某个节点的红色连通分量数量
int solve(int x) {
    memset(book, 0, sizeof(book));
    int cnt = 0;
    int fax = find(x);
    for (int i = head[x], y; i; i = Next[i]) {
        y = ver[i];
        if (c[y] == 'R' && !book[y]) {
            if (book[find(y)] == false) {
                book[find(y)] = true;
                cnt++;
            }
            book[y] = true;
        }
    }
    return cnt;
}

int main() {
    cin >> n >> m;
    scanf("%s", c + 1);

    // 构建图
    for (int i = 1, x, y; i <= m; ++i) {
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }

    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
    }

    int res = 0;

    // 找到红色连通分量数量
    for (int i = 1; i <= n; ++i) {
        if (!book[i] && c[i] == 'R') {
            dfs0(i);
            res++;
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (c[i] == 'R') {
            printf("%d\n", res);
        } else {
            printf("%d\n", res - solve(i) + 1);
        }
    }

    return 0;
}

python

n, m = map(int, input().split())
c = ' '+input().strip()

maxn = 10 ** 5 + 10
head = [0] * (maxn)
ver = [0] * (maxn << 1)
Next = [0] * (maxn << 1)
tot = 1
fa = [0] * (maxn)
book = [False] * (maxn)

# 添加一条边
def add(x, y):
    global tot
    tot += 1
    ver[tot] = y
    Next[tot] = head[x]
    head[x] = tot

# 查找父节点
def find(x):
    if x == fa[x]:
        return x
    fa[x] = find(fa[x])
    return fa[x]

# 合并两个集合
def merge(x, y):
    fax = find(x)
    fay = find(y)
    if fax != fay:
        fa[fax] = fay

# 深度优先搜索，建立红色连通分量
def dfs0(x):
    book[x] = True
    i = head[x]
    while i!=0:
        y = ver[i]
        if c[y] == 'R' and not book[y]:
            merge(x, y)
            dfs0(y)
        i = Next[i]

# 计算某个节点的红色连通分量数量
def solve(x):
    global book
    book = [False] * (maxn)
    cnt = 0
    fax = find(x)
    i = head[x]
    while i != 0:
        y = ver[i]
        if c[y] == 'R' and not book[y]:
            if not book[find(y)]:
                book[find(y)] = True
                cnt += 1
            book[y] = True
        i = Next[i]
    return cnt

# 构建图
for _ in range(m):
    x, y = map(int, input().split())
    add(x, y)
    add(y, x)

for i in range(1, n + 1):
    fa[i] = i

res = 0

# 找到红色连通分量数量
for i in range(1, n + 1):
    if not book[i] and c[i] == 'R':
        dfs0(i)
        res += 1

for i in range(1, n + 1):
    if c[i] == 'R':
        print(res)
    else:
        print(res - solve(i) + 1)

Java

import java.util.*;

public class Main {
    static int maxn = 100_010;
    static int maxm = 2 * maxn;
    static int[] head = new int[maxn];
    static int[] ver = new int[maxm];
    static int[] Next = new int[maxm];
    static int[] fa = new int[maxn];
    static boolean[] book = new boolean[maxn];
    static int tot = 1;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        scanner.nextLine(); // Consume the newline character after reading m

        String c = " " + scanner.nextLine().trim();

        for (int i = 1; i <= n; i++) {
            head[i] = 0;
            fa[i] = i;
            book[i] = false;
        }

        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            add(x, y);
            add(y, x);
        }

        int res = 0;

        for (int i = 1; i <= n; i++) {
            if (!book[i] && c.charAt(i) == 'R') {
                dfs0(i, c);
                res += 1;
            }
        }

        for (int i = 1; i <= n; i++) {
            if (c.charAt(i) == 'R') {
                System.out.println(res);
            } else {
                System.out.println(res - solve(i, c) + 1);
            }
        }
    }

    static void add(int x, int y) {
        ver[tot] = y;
        Next[tot] = head[x];
        head[x] = tot;
        tot++;
    }

    static int find(int x) {
        if (x == fa[x]) {
            return x;
        }
        fa[x] = find(fa[x]);
        return fa[x];
    }

    static void merge(int x, int y) {
        int fax = find(x);
        int fay = find(y);
        if (fax != fay) {
            fa[fax] = fay;
        }
    }

    static void dfs0(int x, String c) {
        book[x] = true;
        int i = head[x];
        while (i != 0) {
            int y = ver[i];
            if (c.charAt(y) == 'R' && !book[y]) {
                merge(x, y);
                dfs0(y, c);
            }
            i = Next[i];
        }
    }

    static int solve(int x, String c) {
        Arrays.fill(book, false);
        int cnt = 0;
        int fax = find(x);
        int i = head[x];
        while (i != 0) {
            int y = ver[i];
            if (c.charAt(y) == 'R' && !book[y]) {
                if (!book[find(y)]) {
                    book[find(y)] = true;
                    cnt += 1;
                }
                book[y] = true;
            }
            i = Next[i];
        }
        return cnt;
    }
}

题目描述

小红有一个无向图，图中有若干个节点是红色，其余为白色。小红想知道，将$i$染成红色，当前图中红色连通块的数量是多少？

输入描述

第一行输入两个正整数$n,m$，代表无向图的节点数和边数。

第二行输入一个长度为$n$的字符串，第$i$个字符为"R"代表节点被染成红色，"W"代表节点被染成白色。

接下来的$m$行，每行输入两个正整数$u,v$，代表节点$u$和节点$v$有一条无向边连接。

请注意，无向图不保证是连通的，而且可能有重边和自环。

$1\le n,m\le 10^5$

$1\le u,v\le n$

输出描述

一共$n$行，第$i$行代表将$i$染红，当前的红色连通块数量

样例

输入

4 4
WRWW
1 2
2 3
1 3
1 4

输出

1
1
1
2