图的遍历

如果要遍历全图,第一个条件就是要确保全图是连通的,所以第一步确定连通块的数量,假设连通块的数量是n,那么如果一个图中存在奇数环,如 (1,2)(2,3)(3,1)那么奇数环就可以遍历全图,而此时需要的边的数量就是n-1,剩下所有的连通块全部连接到奇数环上,比如一个偶数环,无论从那个点出发都无法遍历全图,总会剩下一半的点遍历不到,而连接到奇数环上,就可以,比如第一次进入偶数环的点是x点,那么在奇数环中转一圈进入的就是与x点相连的点,然后可以遍历全图,然后如果一个图中没有奇数环,那么需要构造一个奇数环,也就是偶数环或者不成环的连通块加1条边即可构成奇数环,那么次数需要的边数为n
时间复杂度:

#include<bits/stdc++.h>
using namespace std;
vector<int> tu[300000];
int ans;
int flag[300000];
int flag2[300000];
int flag4;
void dfs(int x,int y,int z)
{
    flag[x]=1;
    flag2[x]=z;
    z=3-z;
    for(int i=0; i<tu[x].size(); i++)
    {
        int j=tu[x][i];
        if(!flag[j])
            dfs(j,y,z);
        else if(flag2[x]==flag2[j])
            flag4=1;
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        int a,b;
        cin>>a>>b;
        tu[a].push_back(b);
        tu[b].push_back(a);
    }
    for(int i=1; i<=n; i++)
    {
        if(!flag[i])
        {
            ans++;
            dfs(i,i,1);
        }
    }
    cout<<ans-flag4;
}

写的代码比较垃圾.........又长跑的又慢..........仅供参考