题意
给出n个点m条边的图 每次只能走两步 问最少加多少条边能完整遍历这个图
思路:
完整遍历首先要保证图联通 这是肯定的 计算联通块的个数 把这几个联通块连在一起就能保证图是联通的 加的边数是联通块个数-1 其次是要保证 每个点都能遍历到 容易想到奇环 如果一开始遍历不到的点 进入奇环后转一圈 就可以遍历到 那么只要判断有无奇环 如果没有的话 就在偶环上加一条边 就构成了奇环
代码
#include <bits/stdc++.h> using namespace std; #define LL long long #define ULL unsigned long long #define mes(x,a) memset(x,a,sizeof(x)); #define sca(a) scanf("%d",&a) #define lowbit(x) x & (-x) #define mk make_pair #define pb(x) push_back(x) #define all(x) (x).begin(),(x).end() #define fi first #define se second #define lson v << 1 #define rson v << 1 | 1 #define pii pair<int, int> const int N = 1e5 + 5; const int M = 1e7+5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double E = 2.7182818284590452353; vector <int> e[N]; int vis[N]; bool flag = 1; void dfs(int x){ for(int i = 0;i < e[x].size();i ++){ int to = e[x][i]; if(vis[to] == -1){ vis[to] = vis[x] ^ 1; dfs(to); }else if(vis[to] == vis[x]){ flag = 0; } } } int main() { int n,m;cin >> n >> m; for(int i = 0;i < m;i ++){ int x,y;cin >> x >> y; e[x].pb(y); e[y].pb(x); } mes(vis,-1); int cnt = 0; for(int i = 1;i <= n;i ++){ if(vis[i] == -1){ ++ cnt ; vis[i] = 0; dfs(i); } } cout << cnt - 1 + flag << '\n'; return 0; }