昨天在学校 oj 上过的版本似乎没有判重,看来还是数据弱了。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e4 + 10, M = 2e5 + 10;
int h[N], e[M], ne[M], idx, globalTime;
enum COLOR {
WHITE, GRAY, BLACK
};
COLOR color[N];
int discoverTime[N], back[N],cnt[N];
bool isRoot[N], st[N];
vector<int> ap;
void dfs_ap(int v, int p){
color[v] = GRAY;
globalTime ++;
discoverTime[v] = globalTime;
back[v] = discoverTime[v];
for(int i = h[v]; i != -1; i = ne[i]){
int j = e[i];
if(color[j] == WHITE){
cnt[v] ++;
dfs_ap(j, v);
if(back[j] >= discoverTime[v] && !isRoot[v] && !st[v]){
st[v] = true;
ap.push_back(v);
}
back[v] = min(back[v], back[j]);
}else{
if(color[j] == GRAY && j != p){
back[v] = min(back[v], discoverTime[j]);
}
}
}
}
void addArc(int x, int y){
e[idx] = y;
ne[idx] = h[x];
h[x] = idx ++;
}
int main(){
int n,m;
cin >> n >> m;
int x, y;
memset(h, -1, sizeof h);
while(m--){
scanf("%d%d", &x, &y);
addArc(x, y);
addArc(y, x);
}
for(int i = 1; i <= n; i ++){
if(color[i] == WHITE){
isRoot[i] = true;
dfs_ap(i, -1);
if(cnt[i] > 1 && !st[i]){
ap.push_back(i);
st[i] = true;
}
}
}
sort(ap.begin(), ap.end());
int len = ap.size();
cout << len << endl;
for(int i = 0; i < len; i ++)cout << ap[i] << " ";
return 0;
}