Vijos P1769 网络的关键边

Description

一个连通的无向图,有些点有A属性,有些点有B属性,可以同时具有.删掉某条边后,如果使得连通块中一些点不具有A,B属性的点,求这些边.

Sol

Tarjan求割边.

首先这些边一定在割边上,然后统计分开的两个连通块中,是否使一边不具有A,B属性的点.

这个只需要DFS一遍,统计该点子树中有多少a,多少b.

判断的时候就是如果 \(a[v]=0,b[v]=0,a[v]=k,b[v]=l\) 这些都合法.

Code

#include<cstdio>

#include<algorithm>

#include<utility>

#include<vector>

#include<iostream>

using namespace std;

const int N = 100005;

#define mpr(a,b) make_pair(a,b)

int n,m,k,l,cnt,tot,ans;

int a[N],b[N],iscut[N],e[N];

int dfsn[N],low[N],d[N],vis[N],out[N];

struct Edge{ int fr,to,id; }edge[N];

vector<Edge> g[N];

inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();

	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }

inline void Add_Edge(int u,int v,int id){

	edge[id]=(Edge){ u,v,id };

	g[u].push_back((Edge){ u,v,id });

	g[v].push_back((Edge){ v,u,id });

}

void Tarjan(int u,int fa){

	dfsn[u]=low[u]=++cnt;

	for(int i=0,lim=g[u].size(),v;i<lim;i++) if((v=g[u][i].to)!=fa){

		if(!dfsn[v]){

			Tarjan(v,u);

			if(low[v]>dfsn[u]) iscut[g[u][i].id]=1;

			low[u]=min(low[u],low[v]);

		}else low[u]=min(low[u],dfsn[v]);

	}

}

void DFS(int u,int fa){

	vis[u]=1,d[u]=d[fa]+1;

	for(int i=0,lim=g[u].size(),v;i<lim;i++) if(!vis[(v=g[u][i].to)]&&v!=fa){

		DFS(v,u);a[u]+=a[v],b[u]+=b[v];

	}

}

int main(){

//	freopen("in.in","r",stdin);

	n=in(),m=in(),k=in(),l=in();

	for(int i=1;i<=k;i++) a[in()]=1;for(int i=1;i<=l;i++) b[in()]=1;

	for(int i=1,u,v;i<=m;i++) u=in(),v=in(),Add_Edge(u,v,i);

	for(int i=1;i<=n;i++) if(!dfsn[i]) Tarjan(i,0);

	for(int i=1;i<=m;i++) if(iscut[i]) e[++tot]=i;

//	for(int i=1;i<=tot;i++) cout<<e[i]<<" "<<edge[e[i]].fr<<" "<<edge[e[i]].to<<endl;

	DFS(1,0);

	for(int i=1;i<=tot;i++){

		int u=edge[e[i]].fr,v=edge[e[i]].to;

		if(d[v]<d[u]) swap(v,u);

		if(a[v]==0||b[v]==0||a[v]==k||b[v]==l) out[++ans]=e[i];

	}

	printf("%d\n",ans);

	for(int i=1;i<=ans;i++) printf("%d\n",out[i]);

	return 0;

}