分析

我们先考虑如何求答案，我们发现其实答案等于 ， 表示集合的个数，就就是连通块的个数，那么这个我们可以通过简单的并查集来维护。现在我们按照思路打一下，嗯。 获得了 96分的好成绩 。考虑我们的复杂度为什么如此高。其实是因为所有边都被我们枚举了一次，但是其中其实有许多无用的边。我们尝试给边定向。如果学习过三元环的朋友，那么后面就好理解了。我们求出每个点的度数，那么当一个点的度数小于 。那么边就由小的指向大的。如果两个都大于 那么就链接双向边。我们考虑为什么是对的。

• 当一个点的度数 那么总边数为 。

• 当一个点的度数 那么我们可以证明这样的点一定不超过 个。所以总的边数为 。

那么我们重新给边定向之后，我们的复杂度就为 。可以通过。良心题，为出题人点赞。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1000,S = 400;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f=1;ch = getchar();}
    while(isdigit(ch)) {x = x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
#define pii pair<int,int> 
int n,m,T,fa[N],vis[N],A[N],du[N];
vector<int> G[N];
pii E[N];
int find(int x) {return !fa[x]?x:fa[x]=find(fa[x]);}
int main() {
    n = read();m = read();T = read();
    for(int i = 1,a,b;i <= m;i++) {
        a = read();b = read();du[a]++;du[b]++;
        E[i] = pii(a,b);
    }
    for(int i = 1;i <= m;i++) {
        int x = E[i].first,y = E[i].second;
        if(du[x] <= S) G[x].push_back(y);
        if(du[y] <= S) G[y].push_back(x);
        if(du[x] > S && du[y] > S) G[y].push_back(x),G[x].push_back(y);
    }
    while(T--) {
        int k = read();
        for(int i = 1;i <= k;i++) A[i] = read(),vis[A[i]] = 1;
        int ans = k;
        for(int i = 1;i <= k;i++) {
            int fx = find(A[i]);
            for(auto y:G[A[i]]) if(vis[y]) {
                int fy = find(y);
                if(fy != fx) ans--,fa[fy] = fx;
            }
        } 
        for(int i = 1;i <= k;i++) fa[A[i]] = 0,vis[A[i]] = 0;
        printf("%d\n",ans);
    }
}