自动搬运

查看原文

来自洛谷，原作者为

	小小小朋友 弱

搬运于2025-08-24 22:32:12，当前版本为作者最后更新于2021-07-04 13:33:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

显然，答案肯定是割边。

tarjan 求出所有割边，在 tarjan 的 dfs 的时候维护出此节点的子树中服务 A 和服务 B 的数量。

如果此子树中并不包含服务 A 或者服务 B ，或者包含了全部服务 A 或者服务 B，那么这个点到这个子树的边即为一条关键边。

此题搬运的时候没有搬运 spj……所以这个代码暂时过不了。

代码

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],dfn[100005],low[100005],cnt,ans,tot,n,m,l,k;
vector<int> v[100005];
vector<int> ans1,ans2;
void tarjan(int u,int fa){//tarjan模板
	dfn[u]=low[u]=++tot;
	for(int nv:v[u]){//C++11语法，遍历子节点
		if(!dfn[nv]){//找到割边
			tarjan(nv,u);
			low[u]=min(low[u],low[nv]);
			if(low[nv]>dfn[u]){
				if(!a[nv]||!b[nv]||a[nv]==l||b[nv]==k){//没有A/B，或者A/B全在子树
					ans++;ans1.push_back(nv);ans2.push_back(u);
				}
			}
			a[u]+=a[nv],b[u]+=b[nv];
		}
		if(nv!=fa){
			low[u]=min(low[u],dfn[nv]);
		}
	}
}
int main(){
	cin>>n>>m>>l>>k;
	for(int i=1;i<=l;i++){int tmp;cin>>tmp;a[tmp]=1;}
	for(int i=1;i<=k;i++){int tmp;cin>>tmp;b[tmp]=1;}
	for(int i=1;i<=m;i++){
		int a,b;cin>>a>>b;
		v[a].push_back(b);v[b].push_back(a);
	}
	tarjan(1,0);
	cout<<ans<<endl;
	for(int i=0;i<ans;i++) cout<<ans1[i]<<' '<<ans2[i]<<endl;
	return 0;
}