描述
给出一个无向连通图，即在任一个点对间存在路径。有的点提供服务a， 有的点提供服务b 。同一个点可能有两种服务类型。每个点必须与提供2种服务的点连通。如果一个边断掉，就可能出现有些点不能被服务到，那么这条边就称为关键边。你的任务是找出关键边数量以及每条关键边。
输入
第一行是整数N,M,K,L (1<=N<=100000, 1<=M<=1000000, 1<=K<=N,1<=L<=N)。N是图节点数；M是边数；k是提供服务a的点个数；L是提供服务b的点个数。第二行有K个数，每个数表示提供服务a的节点。第三行有L个数，每个数表示提供服务b的节点。接下来M行，每行两个不同的数，他们表示一条边的两个节点。
输出
输出文件只有一行为一个整数S，表示关键边的数量。
样例输入
9 10 3 4
2 4 5
4 9 8 3
1 2
4 1
2 3
4 2
1 5
5 6
6 7
6 8
7 9
8 7
样例输出
3
标签
ceoi2005
对于每一个连通分量记录其中有几个a类点和几个b类点。
然后对于每一条割边分成的两个连通分量判一下是不是有没有a类点或者没有b类点的就行了。
代码：
#include<bits/stdc++.h>
#define N 100005
#define M 1000005
using namespace std;
int first[N],dfn[N],low[N],dfs_blocks,n,m,k,l,cnt=0,cnta[N],cntb[N],ans=0;
struct edge{int v,next;}e[M<<1];
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline int min(int a,int b){return a<b?a:b;}
inline void swap(int&a,int&b){a^=b,b^=a,a^=b;}
inline void tarjan(int p,int fa){
dfn[p]=low[p]=++dfs_blocks;
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
if(dfn[v]){low[p]=min(low[p],low[v]);continue;}
tarjan(v,p),low[p]=min(low[p],low[v]);
if(low[v]>dfn[p])if(!cnta[v]||!cntb[v]||cnta[v]==k||cntb[v]==l)++ans;
cnta[p]+=cnta[v],cntb[p]+=cntb[v];
}
}
int main(){
n=read(),m=read(),k=read(),l=read();
for(int i=1;i<=k;++i)cnta[read()]=1;
for(int i=1;i<=l;++i)cntb[read()]=1;
for(int i=1;i<=m;++i){
int u=read(),v=read();
add(u,v),add(v,u);
}
tarjan(1,0);
cout<<ans;
return 0;
}