当前位置:网站首页>E - Don‘t Really Like How The Story Ends

E - Don‘t Really Like How The Story Ends

2022-11-24 21:29:40Demoo.

 

 题意:有n个点,原来有路线,使n个点从开始遍历是1~n的dfs序

但是后来只剩下了m条路,让求最少补多少条路能让他从1开始遍历dfs序仍是1~n

思路:用con来表示当前找的点,ans来表示要添加的路的条数

从1开始遍历,比如我们遍历与u相连的结点v

我们当前遍历的v小于con的话就不用管,继续遍历与u相连的v

如果等于的话,当前要找的结点编号con++

然后遍历他的上一个结点(con-1)

如果大于的话,相当于与u连了一个大于con的编号,那么这个时候我们就得在u上添加一个到con的路了,所以ans++,添加完之后当前找的点编号++,然后遍历当前要找的结点的上一个结点

(这样遍历相当于遍历了从cnt到v)

注意一个细节就是应该在1结点加一个与n+1相连的边(因为我们需要找到n)

#include<bits/stdc++.h>
using namespace std;
#include<vector>
const int N=1e5+10;
int  n,m;
int ans,con;
vector<int> yy[N];
void dfs(int u){
	if(u==n+1)return ;
	for(auto v:yy[u]){
		if(v<con)continue;
		while(v>=con){
			if(v==con){
				con++;
				dfs(con-1);
			}else{
				ans++;
				con++;
				dfs(con-1);
			}
		}
	}
}
void sove(){
	scanf("%d%d",&n,&m);
	ans=0;
	while(m--){
		int a,b;
		scanf("%d%d",&a,&b);
		yy[a].push_back(b);
		yy[b].push_back(a);  
	}
	yy[1].push_back(n+1); 
	for(int i=1;i<=n;i++){
		sort(yy[i].begin() ,yy[i].end() );
	}
	con=2;
	dfs(1);
	printf("%d\n",ans);
	for(int i=1;i<=n;i++) yy[i].clear() ;
	
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		sove();
	}
	return 0;
}

 

原网站

版权声明
本文为[Demoo.]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_61903556/article/details/128002022

随机推荐