题目传送门(内部题7)
输入格式
第一行一个整数T,表示共T组数据。
对于每组数据,第一行两个数n,m表示有n个建筑物,m条道路。
接下来m行,每行两个整数u,v,表示第u个建筑物和第v个建筑物之间相连。
输出格式
对于每组数据,输出共两行。
第一行一个数x表示共有x个必经点(不包括1号点和n号点)。
接下来一行x个数,描述这x个必经点是那些点。按从小到达输出。
注意:如果第一行输出了0,那么接下来你输出的第二行应该只有一个换行符。
样例
样例输入1:
1
4 3
1 2
2 3
3 4
样例输出1:
2
2 3
样例输入2:
1
5 5
1 2
2 3
3 4
4 5
4 1
样例输出2:
1
4
数据范围与提示
$T\leqslant 10$。
$n\leqslant 200,000$。
可能有重边或自环。$m\leqslant n$。
题解
是到这道题,首先,应该想到割点,塔尖缩点必不可少。
但是,必经点一定是割点,但是割点不一定是必经点,因为只有在圆方树上1到n这条链上的点才是必经点。
那么我们应该怎么办呢?
显然可以塔尖缩点,建图,在新图上跑,再找回去,但是实现过于复杂,常数较大。
所以我们考虑另一种做法。
在塔尖算法中,如果一个点的时间戳小于等于它的子节点的回溯值,那它一定是一个割点。
那么,如果一个点的儿子的时间戳小于等于n的时间戳的话才是1到n的路径上的必经点。
你可能会仍给我类似下面这张图:
如果我们先访问了点2,那么点3和点4的时间戳都比点5小,怎么办呢?
访问了点2,如果我们先访问了点3,那么点4还没有被访问过,而点4恰恰是判定点2为割点的条件,而此时点2连割点的条件都没有满足,更不用考虑是不是必经点了。
如果我们先访问了点4,那么点5还没有被访问到,所以也不成立。
代码时刻
#include<bits/stdc++.h> using namespace std; struct rec { int nxt; int to; }e[1000000]; int head[200001],cnt; int n,m; int dfn[200001],low[200001],tot; bool cut[200001]; int ans; void pre_work() { cnt=tot=ans=0; for(int i=1;i<=n;i++) head[i]=dfn[i]=low[i]=cut[i]=0; } void add(int x,int y) { e[++cnt].nxt=head[x]; e[cnt].to=y; head[x]=cnt; } void tarjan(int x) { dfn[x]=low[x]=++tot; int flag=0; for(int i=head[x];i;i=e[i].nxt) { if(!dfn[e[i].to]) { tarjan(e[i].to); low[x]=min(low[x],low[e[i].to]); if(dfn[x]<=low[e[i].to]&&dfn[e[i].to]<=dfn[n])//加一个判定条件 { flag++; if(x!=1||flag>1){ans++;cut[x]=1;} } } else low[x]=min(low[x],dfn[e[i].to]); } } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); pre_work(); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } tarjan(1); printf("%d\n",ans); for(int i=1;i<=n;i++) if(cut[i])printf("%d ",i); puts(""); } return 0; }
不管你怎么说,反正我觉得这个代码比其他人的代码简洁多了~
rp++