【洛谷】P7687 [CEOI2005] Critical Network Lines （tarjan）

链接

P7687 [CEOI2005] Critical Network Lines

分析

1 由本题对关键路径的定义，首先能想到它首先是满足割边（桥）的定义的。
因此我们可以先找出所有的桥，答案是这个集合的一个子集。

2 进一步地，如果当前这条是桥的边满足：它所连接的的两侧 至少有一侧没有两种种类的点，那么如果我们去掉这条边，两侧就不再相连通，缺少点的种类的那一侧无法访问缺的这种种类的点，于是把它加进答案。

依据此思路可以先写tarjan找出所有的桥，再写一个dfs函数统计当前位置下两种点的个数，一边判断。

然而会超时（tle \(\times\) 1）

优化

判断的时候需要在原集合中进行查找。我们于是要对这个查找进行优化。
仔细观察（对于无向连通图的）tarjan和dfs函数，它们的结构惊人的相似，因此我们可以就写一个tarjan函数，边统计边判断当前的桥是否满足题目要求

code

#include      
//luogu p7687 先找到所有的桥，再判断 桥的两边是否只有<=1种 若是才留下 
#define ll long long      
using namespace std;
const int N = 100005;
int n,m,A,B;
int a[N],b[N];
bool aa[N],bb[N];
vectorg[N],v[N];
bool in[N],vis[N];
int cnt,t,e;
int x[10*N],y[10*N];
int rd[N],cd[N];
int dfn[N],low[N],sta[N],f[N];
vector>ans,final;
int dp[N][2];  //0:none  1:A   2:B   3:A+B 

void tarjan(int now,int fa){ //无向图 
	dfn[now]=low[now]=++cnt;
	dp[now][0]+=aa[now];//
	dp[now][1]+=bb[now];//
	for(int i=0;idfn[now]){
				if(dp[x][0]==A||dp[x][0]==0||dp[x][1]==B||dp[x][1]==0){
					ans.push_back(make_pair(x,now));
				}
			}
		}
		else{
			if(fa!=x){ 
				low[now]=min(low[now],dfn[x]);
			}
		}
	}
	
} 

int main(){
	scanf("%d%d%d%d",&n,&m,&A,&B);
	for(int i=1;i<=A;i++) scanf("%d",&a[i]),aa[a[i]]=1;
	for(int i=1;i<=B;i++) scanf("%d",&b[i]),bb[b[i]]=1;
	
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x[i],&y[i]);
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i,i);
		}
	}
	dfs(1,1);
	printf("%d\n",ans.size());
	for(auto i:ans){
		printf("%d %d\n",i.first,i.second);
	}
	return 0;
}