警钟长鸣
查看原帖
警钟长鸣
754516
MSN_04楼主2024/3/25 16:55

rt,此题最恶心的在于有重边,故需要在原普通tarjan中加一个针对父亲访问次数的判断。下方就是个改好的代码供大家参考。

void tarjan(ll dp,ll f){
	dfn[dp]=low[dp]=++tot;
	star[++cnt]=dp;
	vis[f]=0;
	for(int i=0;i<G[dp].size();i++){
		ll x=G[dp][i];
		if(x==f) vis[f]++;
		if(vis[f]<2&&x==f) continue;
		
		if(dfn[x]==0){
			tarjan(x,dp);
			low[dp]=min(low[dp],low[x]);
		}
		else low[dp]=min(dfn[x],low[dp]);
	}	
	if(dfn[dp]==low[dp]){
		int x;
		vector<ll> q;
		q.push_back(dp);
		while(x=star[cnt--]){
			if(x==dp) break;
			q.push_back(x);
		}
		cn++;//记录组数
	   	for(int i=0;i<q.size();i++)ans[cn].push_back(q[i]);//统计答案 
	}
}
2024/3/25 16:55
加载中...