1386：打击犯罪(black)(并查集)

阅读量：

题目描述

在这里插入图片描述

思路：

样例解析：初始的2 2 5表示第一个数字2意味着其后存在两个数值，而这两个数值分别与1及2、5存在关联。若采用正向遍历的方式，需多次运用并查集算法，这可能导致运行时间超出限制。然而，若采取逆向方式，即从n开始逐步遍历至1，并在此过程中添加节点，一旦发现最大节点集合的数量超过n的一半，则应输出k。

代码：

复制代码

    #include<iostream>
    #include<string>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n , kk[1005][1005];
    int f[1005] , t[1005];
    void init()//初始化
    {
    for(int i = 1 ; i <= n ; i++)
    {
        f[i] = i;
        t[i] = 1;

全部评论 (0)

还没有任何评论哟~