tarjan的第二个问题
  • 板块学术版
  • 楼主LonginusMonkey
  • 当前回复9
  • 已保存回复9
  • 发布时间2023/8/4 00:20
  • 上次更新2023/11/3 06:02:28
查看原帖
tarjan的第二个问题
326254
LonginusMonkey楼主2023/8/4 00:20

这个是点双模板代码,问一下28行为什么不能用vec[index].size()代替son,这不是等价的吗?望指正!悬赏关注

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> vec[500100], ans[500100];
int low[500100], dfn[500100], ti, sta[500100], top, tot;
void dfs(int index, int back) {
	low[index] = dfn[index] = ++ti;
	sta[++top] = index;
	int son = 0;
	for(int i=0; i<vec[index].size(); ++i) {
		if(vec[index][i] == back) continue;
		if(!dfn[vec[index][i]]) {
			son++;
			dfs(vec[index][i], index);
			low[index] = min(low[index], low[vec[index][i]]);
			if(low[vec[index][i]] >= dfn[index]) {
				++tot;
				while(sta[top+1]!=vec[index][i]) {
					ans[tot].push_back(sta[top]);
					top--;
				}
				ans[tot].push_back(index);
			}
		} else {
			low[index] = min(low[index], dfn[vec[index][i]]); 
		}
	}
	if(back == 0 && son == 0) {
		ans[++tot].push_back(index);
	}
}
signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i=1; i<=m; ++i) {
		int u, v; cin >> u >> v;
		vec[u].push_back(v); vec[v].push_back(u);
	}
	for(int i=1; i<=n; ++i) {
		if(dfn[i]) continue;
		top = 0;
		dfs(i, 0);
	}
	cout << tot << endl; 
	for(int i=1; i<=tot; ++i) {
		cout << ans[i].size() << " "; 
		for(int j=0; j<ans[i].size(); ++j) {
			cout << ans[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}
2023/8/4 00:20
加载中...