关于 #11
查看原帖
关于 #11
632311
huyangmu楼主2024/10/4 08:06

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e6 + 5;
int n, m, x, y, dfn[N], low[N], id, ans, child;
bool vis[N];
vector<int> G[N];
void tarjan (int x, int fa){
	dfn[x] = low[x] = ++id;
	child = 0; 
	for (int i = 0; i < G[x].size(); ++i){
		int nxt = G[x][i];
		if (dfn[nxt] == 0){
			tarjan (nxt, fa);
			low[x] = min (low[x], low[nxt]);
			if (dfn[x] <= low[nxt] && x != fa) vis[x] = 1;
			if (x == fa) ++child;
		}else low[x] = min (low[x], dfn[nxt]);
	}
	if (x == fa && child > 1) vis[x] = 1;
}
signed main (){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i){
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x); 
	}
	for (int i = 1; i <= n; ++i){
		if (dfn[i] == 0){
			tarjan (i, i);
		}
	}
	for (int i = 1; i <= n; ++i){
		if (vis[i]){
			++ans;
		}
	}
	cout << ans << '\n';
	for (int i = 1; i <= n; ++i){
		if (vis[i] == 1){
			cout << i << ' ';
		}
	}
	cout << '\n';
	return 0;
}

这样是 9292 分。


#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e6 + 5;
int n, m, x, y, dfn[N], low[N], id, ans;
bool vis[N];
vector<int> G[N];
void tarjan (int x, int fa){
	dfn[x] = low[x] = ++id;
	int child = 0; 
	for (int i = 0; i < G[x].size(); ++i){
		int nxt = G[x][i];
		if (dfn[nxt] == 0){
			tarjan (nxt, fa);
			low[x] = min (low[x], low[nxt]);
			if (dfn[x] <= low[nxt] && x != fa) vis[x] = 1;
			if (x == fa) ++child;
		}else low[x] = min (low[x], dfn[nxt]);
	}
	if (x == fa && child > 1) vis[x] = 1;
}
signed main (){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i){
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x); 
	}
	for (int i = 1; i <= n; ++i){
		if (dfn[i] == 0){
			tarjan (i, i);
		}
	}
	for (int i = 1; i <= n; ++i){
		if (vis[i]){
			++ans;
		}
	}
	cout << ans << '\n';
	for (int i = 1; i <= n; ++i){
		if (vis[i] == 1){
			cout << i << ' ';
		}
	}
	cout << '\n';
	return 0;
}

childchild 改成局部变量就过了?为什么?

2024/10/4 08:06
加载中...