由于本人没找到题目，所以只能算是 “笔记” 了。
前置知识：
简要题意：
给定一个无向图，求从 (1) 到 (n) 的必经点。
首先，(1) 到 (n) 的必经点肯定都是割点，因为去掉它们如果还能连通，那它们就不是必经的。
但是，割点并不一定是 (1) 到 (n) 的必经点 ，因为很可能割掉这个点并不影响从 (1) 到 (n) 的路径。
所以，我们采用 ( exttt{Tarjan}) 求割点的类似办法。
即，我们用 ( ext{has}_i) 表示 (i) 的子树（搜索树）中是否存在 (n). 那么 (i) 是必经点的条件即为 (has_i =1) 且 (i) 是割点。
对于 ( ext{has}) 的维护，将在代码中简述。
时间复杂度：(O(n+m)).（这次博主改进了代码，把 ( exttt{set}) 去掉改成桶，因此少了一个 (log)，然后添加了 ( exttt{father}) 让代码看起来更正常）
实际得分：( exttt{Tarjan}) 技巧 ( imes 100).（因为没题可交，至少本人没有找到，有的请评论或私信，博主及时更新）
注：大量的调试代码没有去，因为我花了 (1h) 调试，具体过程 / 问题所在可以看我的 易错集 或者是 心路历程 & 部分感想.
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
vector<int>G[N];
int h[N],tot=0,cnt=0;
int n,m,dfn[N],low[N];
/*set<int>s;*/ bool vis[N];
bool has[N],cut[N];
inline void dfs(int u,int fa) { //正常 Tarjan
// printf("%d %d
",u,fa);
vis[u]=1; if(u==n) has[u]=1; //显然 n 包含自己
bool f=0; low[u]=dfn[u]=++cnt;
for(int i=0;i<G[u].size();i++) {
int v=G[u][i];
if(v==fa) continue;
if(!vis[v]) {
// printf("%d %d %d
",u,fa,v);
dfs(v,u); low[u]=min(low[u],low[v]);
has[u]|=has[v]; //位运算或，表示两个有一个是 1 则为 1 ，否则为 0 (因为子树有的，父节点肯定有啊)
if(has[v] && low[v]>=dfn[u]) f=1; //标记
} else low[u]=min(low[u],dfn[v]);
} if(u!=1 && f) tot++,cut[u]=1; //即必经点
}
int main() {
// freopen("busstop.in","r",stdin);
// freopen("busstop.out","w",stdout);
n=read(); m=n-1;
for(int i=1;i<=m;i++) {
int x=read(),y=read();
G[x].push_back(y);
G[y].push_back(x);
} //for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
dfs(1,1);
// for(int i=1;i<=n;i++) printf("%d ",low[i]); puts("");
// for(int i=1;i<=n;i++) printf("%d ",dfn[i]); puts("");
// for(int i=1;i<=n;i++) printf("%d ",has[i]); puts("");
printf("%d
",tot);
for(int i=1;i<=n;i++)
if(cut[i]) printf("%d ",i);
puts(""); //put(s) 表示输出字符串 s 再换行. s 是空串时，等同于 putchar('
') 但简短一些
/* printf("%d
",s.size());
for(set<int>::iterator i=s.begin();i!=s.end();i++)
printf("%d ",*i); putchar('
');*/
return 0;
}