题目文章来源地址https://www.toymoban.com/news/detail-792835.html
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int maxn = 2e5 + 5, maxm = 2e3 + 5;
int a[maxn];
int nxt;//下一个应该遍历的结点
int res = 0;
int n, m;
vector<int> G[maxn];
void dfs(int u){
if(u == nxt) nxt++;
for(int i = 0; i < G[u].size();){//这里不写i++
int v = G[u][i];
if(v < nxt){//之前遍历过的结点,跳过
i++;
continue;
}
if(v > nxt){
res++;
dfs(nxt);//这里不i++, 等把nxt~v-1的结点遍历完再dfs(v)
/*
1
4 1
1 3
*/
}
else{
dfs(v);
i++;
}
}
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
G[i].clear();
}
res = 0;
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
// if(u == v) continue;
// if(u > v) swap(u, v);
G[u].push_back(v);
G[v].push_back(u);
}
for(int i = 1; i <= n; i++){
sort(G[i].begin(), G[i].end());//按顺序来
}
nxt = 1;
while(nxt <= n){
res++;//向nxt连一条边
dfs(nxt);
}
cout << res - 1 << '\n';//减去向1连的一条边
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while(T--){
solve();
}
}
文章来源:https://www.toymoban.com/news/detail-792835.html
到了这里,关于原先有一个图,dfs序是1,2,...,n, 但是其中一些边被破坏,给定被破坏边后的图,求最少要加几条边,可以使图的dfs序为1,2,...,n的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!