Description
Input
Output
Sample Input
4 4 3 1 4 1 2 1 3 2 3 4 1 2 3 4 3 1 2 3 2 1 2
Sample Output
2 3 2
Data Constraint
分析
这题我们可以用一个链表来搞未加入连通块的点，然后在一个vector里面二分找当前点是否被断边（其实最好用哈希）
然后就裸搜了
听从大佬王的建议用两条队列写了链表（我傻了？）
#pragma GCC optimize(2) #include <iostream> #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; const int N=2e5+10; struct Edge {int u,v; }e[2*N]; int cnt; int n,m,q; vector<int> a[N/2]; queue<int> qv;bool Cmp(Edge a,Edge b) {return a.v<b.v; }int Find(int p,int x) {int l=0,r=a[p].size()-1;if (r<l) return 2147483647;while (l<=r) {int mid=l+r>>1;if (a[p][mid]==x) return a[p][mid];if (a[p][mid]>x) r=mid-1;else l=mid+1;}return a[p][l]; }void Bfs(int v0) {queue<int> qu,q;while (!qu.empty()) qu.pop();while (!q.empty()) q.pop();qu.push(v0);while (!qu.empty()) {int u=qu.front();qu.pop();while (!qv.empty()) {int v=qv.front();qv.pop();if (Find(u,v)!=v) qu.push(v);else q.push(v);}while (!q.empty()) {int p=q.front();q.pop();qv.push(p);}} }int main() {freopen("connect.in","r",stdin);freopen("connect.out","w",stdout);scanf("%d%d%d",&n,&m,&q);for (int i=1;i<=m;i++) {cnt++;scanf("%d%d",&e[cnt].u,&e[cnt].v);e[++cnt].u=e[cnt-1].v;e[cnt].v=e[cnt-1].u;}sort(e+1,e+cnt+1,Cmp);for (int i=1;i<=cnt;i++) a[e[i].u].push_back(e[i].v);for (int i=1;i<=q;i++) {int p;scanf("%d",&p);while (!qv.empty()) qv.pop();for (int j=1;j<=p;j++) {int x;scanf("%d",&x);qv.push(x);}int ans=0;while (!qv.empty()) {int u=qv.front();qv.pop();Bfs(u);ans++;}printf("%d\n",ans);}fclose(stdin);fclose(stdout); }
