侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【并查集】团伙

GabrielxD
2023-04-26 / 0 评论 / 0 点赞 / 193 阅读 / 673 字
温馨提示:
本文最后更新于 2023-04-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

P1892 [BOI2003]团伙

试题 算法提高 团伙


题目描述

现在有 nn 个人,他们之间有两种关系:朋友和敌人。我们知道:

  • 一个人的朋友的朋友是朋友
  • 一个人的敌人的敌人是朋友

现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。

输入格式

第一行输入一个整数 nn 代表人数。

第二行输入一个整数 mm 表示接下来要列出 mm 个关系。

接下来 mm 行,每行一个字符 optopt 和两个整数 p,qp,q,分别代表关系(朋友或敌人),有关系的两个人之中的第一个人和第二个人。其中 optopt 有两种可能:

  • 如果 optoptF,则表明 ppqq 是朋友。
  • 如果 optoptE,则表明 ppqq 是敌人。

输出格式

一行一个整数代表最多的团体数。

样例 #1

样例输入 #1

6
4
E 1 4
F 3 5
F 4 6
E 1 2

样例输出 #1

3

提示

对于 100%100\% 的数据,2n10002 \le n \le 10001m50001 \le m \le 50001p,qn1 \le p,q \le n

解题

方法一:并查集 反集

思路

本题用到了并查集的反集技巧。

开数据范围 nn 两倍长度的并查集数组:

  • ppqq 是朋友:合并 p,qp, q
  • ppqq 是敌人:合并 p+n,qp + n, q ,合并 q+n,pq + n, p

处理完所有关系后,枚举并查集正集范围( 1n1\sim n ),与父节点相同的的节点数量即为并查集所维护图的连通分量,也就是所要求的团体数。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int[] roots;
    static int cnt;

    static int find(int x) {
        return roots[x] == x ? x : (roots[x] = find(roots[x]));
    }

    static void union(int p, int q) {
        roots[find(p)] = find(q);
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); int n = (int) in.nval;
        in.nextToken(); int m = (int) in.nval;
        roots = new int[n * 2 + 1];
        for (int i = 1; i <= 2 * n; ++i) roots[i] = i;
        while (m-- > 0) {
            in.nextToken(); char op = in.sval.charAt(0);
            in.nextToken(); int p = (int) in.nval;
            in.nextToken(); int q = (int) in.nval;
            if (op == 'F') union(p, q);
            else {
                union(p + n, q);
                union(q + n, p);
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (roots[i] == i) ++ans;
        }
        System.out.println(ans);
    }
}
0

评论区