图的遍历

图的遍历
链接：https://ac.nowcoder.com/acm/problem/52275
如果要遍历完整个图的话，就需要整个图联通，就需要这个图中联通块的数量在减1条边；
一个图每个点可以多次遍历的话，只要有奇数环的话就能联通，因此只要判断该图是不是奇数环就行了。用flag来记录这个图是不是奇数环，若果是让flag = 0，否则让flag = 1，最后让结果加上res即可

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;

int n, m, res = 0;
vector<int> adj[N];
int flag = 1, st[N]; 

void dfs(int u) {
    for(auto x : adj[u]) {
        if(st[x] == -1) {   //没被染色 
            st[x] = st[u] ^ 1;
            dfs(x);
        }
        else if(st[x] == st[u]) flag = 0;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    while(m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    memset(st, -1, sizeof st);
    for(int i = 1; i <= n; i++) {
        if(st[i] == -1) {
            res++;      //联通块个数 
            st[i] = 0;   //进行染色 
            dfs(i); 
        }
    }
    printf("%d", res - 1 + flag);
    return 0;
}

判断该图中是否存在奇数环:
首先对st[]初始化为-1，如果遍历到到该点就将其染色成0，并将其子节点染色成1
这里用异或 0 ^ 1 = 1, 只要相邻的两个点的颜色一样则说明其存在奇数环