2020Dash-6

Final Dash

今日水题

题目

T122835必经之路

知识点：简单图论

提及到必经的点，第一反应就是割点，然后算法Targen。

但是：

对吗？有反例吗？割点一定是必经的点吗？必经的点只有割点吗？

做法

我们可以枚举每个点，然后删掉它以后看看能不能从起点走到终点，这样就能依此求出每个必经点了。

30%:N<=100,M<=1000

为什么有这个梯度呢？其实是为了照顾只会floyd的。如何判断能不能从起点走到终点？什么都不会写个floyd也能拿走30分O(n^3)

100%:n<=2000,m<=8000

这个数据floyd过不了，但是我们发现很多方法都能做，比如BFS、DFS，甚至是最短路之类的算法，总之能判断起点能否走到终点就行了O(N*M)

代码

const int N=8000+500;
struct data{
	int next,to;
}d[N*4];
int n,m,ans,cross[N];
int cnt=0,head[N*2];
int pand,vis[N];
inline void add(int x,int y){
	cnt++;
	d[cnt].to=y;
	d[cnt].next=head[x];
	head[x]=cnt;
}
void dfs(int p,int crs){ //全图遍历，能否到达终点 
	if(p==n){pand=1; return;}
	vis[p]=1;
	for(int i=head[p]; i; i=d[i].next){
		if(!vis[d[i].to] && d[i].to!=crs) dfs(d[i].to,crs);
		if(pand) return;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1; i<=m; i++){
		int x,y; cin>>x>>y;
		add(x,y); add(y,x);
	}
	for(int i=2; i<n; i++){ //不包括起点&终点 
		pand=0; memset(vis,0,sizeof(vis));
		dfs(1,i);
		if(!pand) ans++,cross[ans]=i; //不能到达终点说明i为必经之路 
	}
	cout<<ans<<endl;
	for(int i=1; i<=ans; i++) cout<<cross[i]<<endl; 
	return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议