算法(二分 + bfs)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1010;

vector<vector<int>> grap;//图
vector<bool> visited;
int n;

int bfs(int start){
    //起始点已经被打击，标记
    visited[start] = true;

    //找到与这个起点团伙相联系的团伙
    //使用队列
    queue<int> q;
    q.push(start);

    //定义一个countSize记录个数
    int countSize = 0;

    while(!q.empty()){
        int index = q.front();
        q.pop();

        countSize ++;

        //找到与这个起点团伙相联系的团伙
        for (int neighbor : grap[index]){
            if (!visited[neighbor]){
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    return countSize;
}

bool check(int k){

    //记住要将visited重置
    fill(visited.begin(), visited.end(), false);

    //前k个全部被打击， 用visited标记为true，表示被打击
    for (int i = 1; i <= k; i ++){
        visited[i] = true;
    }

    int maxSize = 0;//记录最大的集团size

    for (int i = 1; i <= n; i ++){
        //从编号1开始到n， 如果说这个团伙没有被打击，就看看他所在的集团size多大，使用bfs
        if (!visited[i]){
            //我们只需要传入起始点
            // bfs(i);
            //求最大
            maxSize = max(maxSize, bfs(i));
        }
    }

    return maxSize <= n / 2;
}


int main(){


    cin >> n;
    grap.resize(n + 1);
    visited.resize(n + 1, false);
    //建图
    for (int i = 1; i <= n; i ++){
        int a;
        cin >> a;
        for (int j = 0; j < a; j ++){
            int neighbor;
            cin >> neighbor;
            grap[i].push_back(neighbor);
        }
    }

    //二分找最小k
    int left = 1, right = n, result = n;
    while(left <= right){
        //中间
        int mid = (left + right) >> 1;
        //假设是中间mid是最小k，这里check作用是检查，n个中，打点1-mid个后，查看mid后的集团中最大的一个 size <= n / 2?
        if (check(mid)){
            //检查是小于等于n/2的，向更小的移动，万一还有更小的
            //记录
            result = mid;
            right = mid - 1;
        }else{
            //不满足，说明还要多打击点，向右移动
            left = mid + 1;
        }
    }

    //输出result，表示打击到最小的k这里就可以满足条件（即后续集团中的最大的不超过n/2）
    cout << result << endl;



    return 0;
}