#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;
}
这样是 92 分。
#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;
}
把 child 改成局部变量就过了?为什么?