题目链接：
http://172.16.0.132/senior/#main/show/5875
题目:
题解：
注意这题只能经过开放的港口
我们考虑用vector存下每个点不能到的点，并把并让vector里面的元素升序排序，这样我们就可以二分查找一个点是否与另外一个点相连
接下来我们对于每一个开放的港口bfs，每次bfs都把属于这个连通块的港口去掉
考虑开两个队列来bfs，队列1存储的是当前连通块里还没有拓展的点，队列2里存储的是还剩下的点，看看代码就可以理解了
#include<algorithm> #include<cstring> #include<cstdio> #include<iostream> #include<vector> #include<queue> using namespace std;const int N=1e5+15; int n,m,t; struct E{int x,y; }e[N<<2]; vector <int> p[N]; queue <int> Q; inline int read(){char ch=getchar();int s=0,f=1;while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}return s*f; } bool cmp(E a,E b){return a.x<b.x||(a.x==b.x&&a.y<b.y);} int find(int u,int v){int l=0,r=p[u].size()-1;if (l>r) return -1;while (l<=r){if (l==r) return p[u][l];int mid=l+r>>1;if (p[u][mid]>v) r=mid-1;else if (p[u][mid]<v) l=mid+1;else if (p[u][mid]==v) return p[u][mid];}return p[u][l]; } void bfs(int x){queue <int> qq,q;qq.push(x);while (!qq.empty()){int u=qq.front();qq.pop();while (!Q.empty()){int v=Q.front();Q.pop();if (find(u,v)!=v) qq.push(v);else q.push(v);}while (!q.empty()){int v=q.front();q.pop();Q.push(v);}} } int main(){freopen("connect.in","r",stdin);freopen("connect.out","w",stdout);n=read();m=read();t=read();int cnt=0;for (int i=1;i<=m;i++){++cnt;e[cnt].x=read();e[cnt].y=read();++cnt;e[cnt].x=e[cnt-1].y;e[cnt].y=e[cnt-1].x;}sort(e+1,e+1+cnt,cmp);for (int i=1;i<=cnt;i++) p[e[i].x].push_back(e[i].y);while (t--){int k=read(),ans=0;while (!Q.empty()) Q.pop();for (int i=1;i<=k;i++){int s=read();Q.push(s);}while (!Q.empty()){int s=Q.front();Q.pop();bfs(s);++ans;}printf("%d\n",ans);} return 0; }
