描述

给出一个无向连通图，即在任一个点对间存在路径。有的点提供服务a， 有的点提供服务b 。同一个点可能有两种服务类型。每个点必须与提供2种服务的点连通。如果一个边断掉，就可能出现有些点不能被服务到，那么这条边就称为关键边。你的任务是找出关键边数量以及每条关键边。

输入

第一行是整数N,M,K,L (1<=N<=, 1<=M<=, 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

显然先把所有割边求出来

 

同时对于所有每一个点维护一个子树中红色和蓝色的数量

 

如果一个点的子树中没有（或有全部）红色或者蓝色

 

那么这个点与子树相连的边就是一个关键边

 

所以dfs的时候统计一下就是了

 

#include<bits/stdc++.h> using namespace std; inline int read(){ char ch=getchar(); int res=0; while(!isdigit(ch))ch=getchar(); while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar(); return res; } int adj[],nxt[],to[],a[],b[],dfn[],low[],cnt,ans,tot,n,m,l,k; inline void addedge(int u,int v){ nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v; nxt[++cnt]=adj[v],adj[v]=cnt,to[cnt]=u; } inline void tarjan(int u,int fa){ dfn[u]=low[u]=++tot; for(int e=adj[u];e;e=nxt[e]){ int v=to[e]; if(!dfn[v]){ tarjan(v,u); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]){ if(!a[v]||!b[v]||a[v]==l||b[v]==k){ ans++; } } a[u]+=a[v],b[u]+=b[v]; } if(v!=fa){ low[u]=min(low[u],dfn[v]); } } } int main(){ n=read(),m=read(),l=read(),k=read(); for(int i=1;i<=l;i++){ a[read()]=1; } for(int i=1;i<=k;i++){ b[read()]=1; } for(int i=1;i<=m;i++){ int u=read(),v=read(); addedge(u,v); } tarjan(1,0); cout<<ans; return 0; }