Tarjan算法的一个小问题:else那里的判断条件为什么不同
  • 板块学术版
  • 楼主HaloisAWA
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/11/18 11:03
  • 上次更新2024/11/18 15:32:38
查看原帖
Tarjan算法的一个小问题:else那里的判断条件为什么不同
1420058
HaloisAWA楼主2024/11/18 11:03

求割点的是v!=fa:

void tarjan(int u,int fa) {
	int son = 0;
	dfn[u] = low[u] = ++cnt;
	for (int i = 0;i < g[u].size();i ++) {
		int v = g[u][i];
		if (!dfn[v]) {
			++ son;
			tarjan(v,u);
			low[u] = min(low[u],low[v]);
			if (low[v] >= dfn[u] && u != root) iscut[u] = true;//////
		} else if (v != fa) low[u] = min(low[u],dfn[v]);//
	}
	if (u == root && son >= 2) iscut[u] = true;//////
	return;
}

求强连通分量的是!sccno[v]:

#include<bits/stdc++.h>
using namespace std;
int n,m,ut,vt,wt,root,dfn[500010],low[500010],sccno[500010],cnt,cntsccno;
vector<int> g[500010];
stack<int> s;
void tarjan(int u,int fa) {
	low[u] = dfn[u] = ++cnt;
	s.push(u);
	for (int i = 0;i < g[u].size();i ++) {
		int v = g[u][i];
		if (!dfn[v]) {
			tarjan(v,u);
			low[u] = min(low[u],low[v]);
		} else if (!sccno[v]) low[u] = min(low[u],dfn[v]);
	}
	if (low[u] == dfn[u]) {
		++ cntsccno;
		while (s.top() != u) {
			sccno[s.top()] = cntsccno;
			s.pop();
		}
		sccno[s.top()] = cntsccno;
		s.pop();
	}
	return;
}
int main() {
	scanf("%d%d",&n,&m);
	for (int i = 1;i <= m;i ++) {
		scanf("%d%d",&ut,&vt);
		g[ut].push_back(vt);
		g[vt].push_back(ut);
	}
	for (int i = 1;i <= n;i ++)
		if (!dfn[i]) tarjan(i,0);
	
	return 0;
}

2024/11/18 11:03
加载中...