打击犯罪 逆向思维

解题思路:逆序列添加进图中当添加到m的时候图中的犯罪团伙数量不超过n/2时说明还可以继续添加否则这个此时的m必须删除  且为最小值

注意事项:这个题目要求 求的就是最小的k 因为把k删除后最大集合的数量不超过n/2  所以把比k大的添加进去更不会超过n/2  所以选着逆向添加i（n~1）添加一次比较此时的团伙数量与n/2的大小  大于n/2  就返回此时的i值就是答案
参考代码:

#include<bits/stdc++.h>

#define x first

#define y second

using namespace std;

const long double PI = acos(-1);

//#define int long long

#define pb push_back

#define point(x) setiosflags(ios::fixed)<<setprecision(x)

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;// 1e19

typedef pair<int, int> PII;

ll st[1005],siz[1005];

int find(ll x){

    return st[x]==x?x:st[x]=find(st[x]);

}

void merg(ll x,ll y){

    ll fx=find(x),fy=find(y);

    if(fx!=fy){

        siz[fy]+=siz[fx];

        st[fx]=fy;

    }

}

void solve(){

    ll n;cin>>n;

    vector<vector<ll>>a(n+1);

    for(int i=1;i<=n;i++){

        st[i]=i;

        siz[i]=1;

    }

    for(int i=1;i<=n;i++){

        ll t;cin>>t;

        for(int j=1;j<=t;j++){

            ll u;cin>>u;

            a[i].push_back(u);

        }

    }

    ll mx=0;

    for(int i=n;i>=1;i--){//逆着添加

        for(int j=0;j<a[i].size();j++){

            if(a[i][j]<i)continue;//小于i的边都还没有加入  所以continue

            merg(i,a[i][j]);//合并

        }

        for(int j=1;j<=n;j++){

            if(j<i)continue;

            if(j==st[j]){

                mx=max(mx,siz[j]);

            }

        }

        if(mx*2>n){

            cout<<i<<"\n";return;

        }

    }

}

int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    int tt = 1;

    // init();

    //   cin >> tt;

    while (tt--) solve();

    return 0;

}