当处理 F (朋友)的时候,直接合并
处理 E (敌人)的时候,先使用 map 进行记录,然后再一次性合并,注意使用 map 记录的时候需要双向记录(互为敌人关系)
例如题目的例子,当处理完输入的时候,应该有如下的映射关系
1 : [2,4]
2 : [1]
4 : [1]
import java.util.*;
import java.io.*;
class Main {
static int N = 10009;
static int[] p = new int[N];
static Map<Integer, Set<Integer>> map = new HashMap<>();
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(reader.readLine());
for (int i = 1; i <= n; i++) {
p[i] = i;
}
int m = Integer.parseInt(reader.readLine());
for (int i = 0; i < m; i++) {
String[] s = reader.readLine().split(" ");
if (s[0].equals("F")) {
int p = Integer.parseInt(s[1]);
int q = Integer.parseInt(s[2]);
meger(p, q);
} else if (s[0].equals("E")) {
int p = Integer.parseInt(s[1]);
int q = Integer.parseInt(s[2]);
Set<Integer> pSet = map.getOrDefault(p, new HashSet<Integer>());
pSet.add(q);
map.put(p, pSet);
Set<Integer> qSet = map.getOrDefault(q, new HashSet<Integer>());
qSet.add(p);
map.put(q, qSet);
}
}
process();
Set<Integer> set = new HashSet<>();
for (int i = 1; i <= n; i++) {
set.add(find(i));
}
writer.write(set.size() + " ");
reader.close();
writer.flush();
writer.close();
}
private static int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
private static void meger(int a, int b) {
p[find(a)] = p[find(b)];
}
private static void process() {
Set<Integer> keys = map.keySet();
for (Integer key : keys) {
List<Integer> list = new ArrayList<>(map.get(key));
if (list.size() == 1) continue;
for (int i = 0; i < list.size() - 1; i++) {
meger(list.get(i), list.get(i + 1));
}
}
}
}