定义x的半必经点为某个x在DFS树上的祖先y，且保证在y---x路径上删除除端点外的任意一点后仍然存在路径从y到x，令semi(x)为所有y中dfn最小的

考虑半必经点定理：

对于一点y，x∈pre(y)：

①dfn[x]<dfn[y]，x即为y在DFS树上的祖先，根据定义：if(dfn[x]<dfn[semi[y]])semi[y]=x;

②dfn[x]>dfn[y]，x不为y的祖先，此时对于任意x的祖先z，满足dfn[z]>dfn[y]：if(dfn[semi[z]]<dfn[semi[y]])semi[y]=semi[z]

这里有几个地方需要解释一下

一、为什么要dfn[z]>dfn[y]：考虑u=lca(x,y)，x所属的是一个较晚被dfs到的子树，如果某个z是x的祖先，且dfn[z]<dfn[y]，那么此时z必为y在DFS树上的祖先，那么直接将z删去便可使semi(z)无法到达y，与定义不符

二、这样子获得的semi[y]一定为y的祖先么：x所属的子树较晚被dfs到，故获得的semi必为y的祖先

必经点定理相当直观，不叙述

这玩意就算考也不会太难吧。。。

whoknows

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define NN 100001
#define MM 1000000
struct chain
{
	int ver[NN],next[MM<<1],to[MM<<1],tot;bool f[MM<<1];
	void addedge(int from,int t,bool v)
	{next[++tot]=ver[from];to[tot]=t;f[tot]=v;ver[from]=tot;}
}G,dom;
int dfn[NN],clk,idom[NN],semi[NN],fa[NN],id[NN];
struct Ufs
{
	int p[NN],best[NN];
	int getf(int x)
	{
		if(x==p[x])return x;
		int t=getf(p[x]);
		if(dfn[semi[best[x]]]>dfn[semi[best[p[x]]]])best[x]=best[p[x]];
		p[x]=t;
		return p[x];
	}
	int getbest(int x)
	{getf(x);return best[x];}
}ufs;
int n,m;
void dfs(int o)
{
	dfn[o]=++clk;id[clk]=o;
	for(int i=G.ver[o];i;i=G.next[i])
		if(!dfn[G.to[i]]&&G.f[i])
		{fa[G.to[i]]=o;dfs(G.to[i]);}
}
bool flag[NN];
void read(int& a)
{
	static char t;
	t=getchar();a=0;
	while(t<'0'||t>'9'){t=getchar();}
	while(t>='0'&&t<='9')
	{a=a*10+(t-'0');t=getchar();}
}
int main()
{
//	scanf("%d%d",&n,&m);
	read(n);read(m);
	for(int i=1;i<=m;i++)
	{
		int a,b;//scanf("%d%d",&a,&b);
		read(a);read(b);
		G.addedge(a,b,1);
		G.addedge(b,a,0);
	}
	dfs(1);
	for(int i=1;i<=n;i++)ufs.p[i]=i,ufs.best[i]=i,semi[i]=i;
	for(int i=n;i>1;i--)
	{
		int tmp=2100000000;
		for(int t=G.ver[id[i]];t;t=G.next[t])
		{
			if(G.f[t])continue;
			if(dfn[semi[ufs.getbest(G.to[t])]]<tmp)
			{
				tmp=dfn[semi[ufs.getbest(G.to[t])]];
			}
		}
		semi[id[i]]=id[tmp];
		dom.addedge(semi[id[i]],id[i],1);
		for(int t=dom.ver[fa[id[i]]];t;t=dom.next[t])
		{
			if(dfn[semi[ufs.getbest(dom.to[t])]]<dfn[fa[id[i]]])
				idom[dom.to[t]]=ufs.getbest(dom.to[t]);
			else idom[dom.to[t]]=semi[dom.to[t]];
		}
		dom.ver[fa[id[i]]]=0;
		ufs.p[id[i]]=fa[id[i]];
	}
	semi[1]=1;idom[1]=0;
	for(int i=2;i<=n;i++)
		if(idom[id[i]]!=semi[id[i]])
			idom[id[i]]=idom[idom[id[i]]];
	int ans=0;
	for(int i=2;i<=n;i++)
		if(!flag[idom[i]]){++ans;flag[idom[i]]=true;}
	
	printf("%d\n",ans);
	for(int i=1;i<=n;i++)
		if(flag[i])
		{
			ans--;
			if(ans==0)printf("%d\n",i);
			else printf("%d ",i);
		}
}