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