比赛链接：https://vjudge.net/contest/777735#problem/A。
割点
介绍
如果从无向图中删去一个点之后，图里的连通分量的数量增加了，那么删去的这个点就被称之为割点。
暴力做法，考虑依次删除每个点，再去数连通分量的个数，判断是否为割点，那么时间复杂度就是 \(O(nm)\) 的，太慢了。一般都是用 Tarjan 做到 \(O(n+m)\) 找割点的。
做法
Tarjan 时，会在 DFS 的过程中维护 \(dfn\) 和 \(low\) 两个信息，其中 \(low_u\) 是指从 \(u\) 出发且最多用反祖边向上走一步的情况下能到达的最小的时间戳。
如果一个点 \(u\)，有子节点 \(v\) 不能回到比 \(u\) 更高的节点，那么 \(u\) 就是割点。因为删掉 \(u\) 之后，\(v\) 所在的子树没有反祖边可以连回来，那么图的连通分量数量就会增多，那么 \(u\) 就是割点咯。
我们可以用 \(low\) 和 \(dfn\) 两个数组快速判断是否能连回来，如果 \(low_v \ge dfn_u\) 就代表 \(v\) 这个子节点连不上去了。
这个判断法则只在非根节点时成立。
根节点需要特殊处理。如果根节点在 DFS 树上有两个或更多子节点，根节点是割点，否则如果只有一个子节点就不是割点。证明过于显然所以不写了。
实现
我在代码中用 \(id\) 表示上文中提到的 \(dfn\)。
void DFS(int u,int fa){id[u]=(++tot),low[u]=id[u];int cnt=0;for(int v:g[u]){if(v==fa)continue;if(id[v])low[u]=min(low[u],id[v]);else{DFS(v,u),cnt++;low[u]=min(low[u],low[v]);if(fa&&low[v]>=id[u])cut[u]=1;}}if(!fa&&cnt>1)cut[u]=1;return;
}