题意:一个无向图,如果删除一个点之后剩下的图是一棵树,那么这个点是毒瘤点,问哪些点是毒瘤点
------------
- 删除一个点之后,剩下$n-1$个点构成的树有$n-2$条边,所以毒瘤点的度数一定是$m-n+2$
- 树是连通图,所以毒瘤点一定不是图的割点
$tarjan$求出割点之后判断即可
```
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=1e5+5;
struct node
{
int to,nxt;
}edge[N<<1];
int n,m,num,ans,head[N],d[N],fa[N],dfn[N],low[N],tim,cut[N];
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline void add_edge(int from,int to)
{
edge[++num]=(node){to,head[from]};
head[from]=num; ++d[to];
}
void tarjan(int k)
{
dfn[k]=low[k]=++tim; int cnt=0;
for (reg int i=head[k];i;i=edge[i].nxt)
{
int v=edge[i].to;
if (!dfn[v])
{
fa[v]=fa[k]; tarjan(v);
low[k]=min(low[k],low[v]);
if (low[v]>=dfn[k]&&k!=fa[k]) cut[k]=1;
if (k==fa[k]) ++cnt;
}
low[k]=min(low[k],dfn[v]);
}
if (k==fa[k]&&cnt>1) cut[k]=1;
}
int main()
{
n=read(),m=read();
for (reg int i=1;i<=m;i++)
{
int x=read(),y=read();
add_edge(x,y); add_edge(y,x);
}
for (reg int i=1;i<=n;i++) fa[i]=i;
for (reg int i=1;i<=n;i++) if (!dfn[i]) tarjan(i);
for (reg int i=1;i<=n;i++)
if (d[i]==m-n+2&&!cut[i]) ++ans;
printf("%d\n",ans);
for (reg int i=1;i<=n;i++)
if (d[i]==m-n+2&&!cut[i]) printf("%d ",i);
return 0;
}
```