D16 Tarjan 割点

/*【参考程序】
割点判定法则: 无向图中存在x的一个子节点y，满足dfn[x] <= low[y]，x就是割点。 
dfn[x] <= low[y] 的意思：y无法追溯到比x早遍历的点，注意不是low[x]<=low[y]
特殊：x为搜索树的根时，必须有两个及以上子节点y满足 dfn[x] <= low[y]
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
vector<pair<int,int>>G[N];int cut[N],root;
int tsp,dfn[N],low[N];
void tarjan(int x,int in_id)
{
	dfn[x]=low[x]=++tsp;
	int child=0;
	for(auto i:G[x])if(i.second!=in_id)
	{
        int y=i.first,id=i.second;
		if(dfn[y]==0)
		{
			tarjan(y,id);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<=low[y])
			{
				child++;
				if(x!=root)
				{
					cut[x]=1;
				}
				else
				{
					if(child>1)cut[x]=1;
				}
				//if(x!=root || child>1)cut[x]=1;
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back({y,i});
		G[y].push_back({x,i});
	}
	tsp=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
	memset(cut,0,sizeof(cut));
	for(int i=1;i<=n;i++)if(dfn[i]==0)root=i,tarjan(i,0);
	
	int ans=0;for(int i=1;i<=n;i++) if(cut[i]==1)ans++;
	printf("%d\n",ans);

	for(int i=1;i<=n;i++) if(cut[i]==1)printf("%d ",i);

    return 0;
}

/*【参考程序】
割点判定法则: 无向图中存在x的一个子节点y，满足dfn[x] <= low[y]，x就是割点。 
dfn[x] <= low[y] 的意思：y无法追溯到比x早遍历的点，注意不是low[x]<=low[y]
特殊：x为搜索树的根时，必须有两个及以上子节点y满足 dfn[x] <= low[y]
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10,M=1e5+10;
struct node{int x,y,pre;}a[M*2];int last[N],alen;
void ins(int x,int y){alen++;a[alen]=node{x,y,last[x]};last[x]=alen;}

int id,cnt,dfn[N],low[N],dcc[N],cut[N],root;
void tarjan(int x,int in_edge)
{
	dfn[x]=low[x]=++id;
	int child=0;
	for(int k=last[x];k;k=a[k].pre)if(k!=(in_edge^1))
	{
		int y=a[k].y;
		if(dfn[y]==0)
		{
			tarjan(y,k);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<=low[y])
			{
				child++;
				if(x!=root || child>1)cut[x]=1;
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	alen=1;memset(last,0,sizeof(last));
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);ins(x,y),ins(y,x);
	}
	id=cnt=0;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
	memset(cut,0,sizeof(cut));
	for(int i=1;i<=n;i++)if(dfn[i]==0)root=i,tarjan(i,0);
	
	int ans=0;for(int i=1;i<=n;i++) if(cut[i]==1)ans++;
	printf("%d\n",ans);
	for(int i=1;i<=n;i++) if(cut[i]==1)printf("%d ",i);
    return 0;
}