链接:
@[toc]

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld

题目描述

小sun最近为了应付考试,正在复习图论,他现在学到了图的遍历,觉得太简单了,于是他想到了一个更加复杂的问题:

无向图有n个点,从点1开始遍历,但是规定:按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法,不一定能够遍历整个图,所以现在小sun想问你,最少加几条边,可以完整的遍历整个图。

输入描述:
第一行两个整数n,m代表图的点数和边数。

接下来m行,每行两个整数u,v代表u,v有边相连(无向边)
输出描述:
输出一行,代表最少要添加的边数。
示例1
输入

5 4
1 2
2 3
3 4
4 5

输出

1

示例2
输入

5 5
1 2
2 3
3 4
4 5
1 5

输出

0

备注:
数据范围:
3≤n≤1e5, 2≤m≤1e5
1≤u,v≤n
图中点的编号从1到n。

走两步的意思:
比如现在有两条边:(1,2),(2,3),从1开始走,只能走到1或者3。
(1->2->3),(1->2->1)

题解

首先,所有点都能到达,也就是图要连通,不连通的话走都走不到肯定不行,所以加边来连通它们。加边数就是现在存在的连通块的数量-1
都连通之后,每次两步两步的走,所走到的点都是偶数点,而奇数点无法走到,所以我们需要构造一个环,使得可以通过环从偶数点迈到奇数点,然后走的就全是奇数点了,这样全部都走完
注意,所连成的环如果是偶环,通过环走到的还是偶数,所以要构成奇环,把一个单独隔开剩下的不就成奇数了

总结下,答案就是连通块的个数+(0/1)
如果存在奇数环就加0,如果没有需要我们现构造,就加1
!((vis[v] - vis[u]) & 1)flag=0;
如果vis[v]-vis[u]的结果ans是偶数,ans&1就是0,!0=1,所以flag=0,也就是v到u的距离是偶数,再加上一个u到v的边就构成奇环,所以不用加一,表示flag=0

代码:

#include<bits/stdc++.h>
#include<bitset>
using namespace std;
typedef long long ll; 
const int maxn = 100007;
struct node {
    int v,next;
}edge[maxn*2];
int head[maxn],cnt;
bool flag = 1;
int vis[maxn];


void add(int u,int v) {

    edge[++cnt].v = v;

    edge[cnt].next = head[u];

    head[u] = cnt;
}

void dfs(int u,int fa) {
    vis[u] = vis[fa] + 1;
    for(int i = head[u];i;i = edge[i].next) 
    {
        int v ;
        v= edge[i].v;
        if(v == fa) continue;
        if(vis[v]) 
        {
            if(!((vis[v] - vis[u]) & 1) ) flag = 0;
            continue;
        }
        dfs(v,u);
    }
    return;
}

int main() {

    int n,m,ans = 0;
    cin>>n>>m;
    for(int i = 1;i <= m;++i) 
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }

    for(int i = 1;i <= n;++i) 
    {
        if(vis[i]) continue;
        ans++;
        dfs(i,0);
    }
    cout<<ans - 1 + flag;
    return 0;
}