今天闲着没事打了一发割点代码,没过样例后对着zty神仙的题解看了几遍,改了后差不多主体部分是一样的除了变量,但还是没过样例,来学术版请教一下神仙们/kel
#include<bits/stdc++.h>
using namespace std;
int dfn[100010], low[100010], pa[100010], n, m, cnt = 0, tot = 0;
bool vis[100010];
vector<int>l[100010];
set<int>ans;
void tarjan(int u)
{
vis[u] = false;
low[u] = dfn[u] = ++ cnt;
int child = 0;
for(int i = 0;i < l[u].size();i ++)
{
int v = l[u][i];
if(vis[v])
{
child ++;
pa[v] = u;
tarjan(v);
low[u] = min(low[u], low[v]);
if ((low[v] >= dfn[u] and pa[u] != u))
{
ans.insert(u);
tot ++;
}
}
else if(pa[u] != v)low[u] = min(low[u], dfn[v]);
}
if(pa[u] == u and child >= 2)
{
ans.insert(u);
tot ++;
}
}
int main()
{
memset(vis, true, sizeof(vis));
cin>>n>>m;
for(int i = 1;i <= m;i ++)
{
int x, y;
cin>>x>>y;
l[x].push_back(y);
l[y].push_back(x);
}
set<int>::iterator it;
for(int i = 1;i <= n;i ++)
{
if(!vis[i])
{
pa[i] = i;
cnt = 0;
tarjan(i);
}
}
cout<<tot<<endl;
for(it=ans.begin();it!=ans.end ();it++)
{
cout<<*it<<' ';
}
return 0;
}
感觉马蜂还行就不加注释了吧