[AcWing] 395. 冗余路径 边双连通分量VCC Tarjan

前言

传送门 :

思路

使用 T a r j a n Tarjan Tarjan求边双连通分量,计算出所有叶子节点

叶子节点为 缩点后的VCC之后度数为 1 1 1的点

答案即为 c n t + 1 / 2 cnt+1 /2 cnt+1/2

Mycode

map mp;
const int N = 5e3+10;
vector g[N];
int dnt[N],low[N];
//dnt表示当前到达的点u low表示从u节点出发能遍历到的最小时间戳
int id[N],d[N];
//id表示 双连通分量的编号,d为节点i的度
bool is_bridge[N];
stack stk;
int dcc_cnt;//双连通分量
int tempstamp;//时间戳
int n,m;
void tarjan(int u,int from){
	low[u] = dnt[u] = ++tempstamp;
	stk.push(u);
	
	for(auto j : g[u]){
			if(!dnt[j]){
			tarjan(j,i);
			low[u] = min(low[u],low[j]);
			//j节点永远走不到u节点  只能从u走到j
			//说明 u - j 是一个桥边
			if(dnt[u] >n>>m;
	for(int i=1;i>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	
	for(int i=1;i