每日一题 5.21 图的遍历

对于这一题，一个图如果能被跳两步走完
首先要图是联通的 即把连通块都连起来 ans=连通块数-1；
在然后，如果这个图有奇数环的话 我们走两个循环就可以把图都走到
如果没有的话 就加一条边形成奇数环 ans+=flag;
答案就出来了

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int const N=2e5+5;
int n,tot,du[N],head[N],nex[N<<1],to[N<<1],vis[N];///链式前向星
void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}

void  dfs(int u,int x)
{
     vis[u]=x;
     for(int j=head[u];j;j=nex[j])///遍历i起点的每一条边
     {
                int v=to[j];///连接的点
                if(!vis[v]) 
                {
                    dfs(v,x*-1);
                }
                if(vis[v]==x) flag=0;///有奇数环
     }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);

    }
    int ans=0,flag=1;
    for(int i=1;i<=n;i++)
    {
        ans++;
        if(vis[i]==0)///没到过 新联通块
        {
           dfs(i,1);
        }
    }
    printf("%d\n",ans-1+flag);
}