hdu 3478（判断奇环）

题意：给你一个无向图，问你有没有可能存在一个奇环连接所有的节点。

分析：好久没写博客了，这个好习惯还是要继续保持的！这道题通过转化之后就是问你有没有存在一个奇环连接所有的节点，这里用到的方法是染色法，这是一个做题时的技巧，掌握好久ok了！

代码实现：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<queue>

using namespace std;

vector<int>edge[];

int n,m,s,visited[];

int solve()

{

    int i,p,x,flag=;

    queue<int>Q;

    memset(visited,,sizeof(visited));

    Q.push(s);

    visited[s]=;

    while(!Q.empty())

    {

        p=Q.front();

        Q.pop();

        for(i=;i<edge[p].size();i++)

        {

           x=edge[p][i];

           if(visited[x]==)

           {

               visited[x]=-visited[p];

               Q.push(x);

           }

           else if(visited[x]==visited[p])//判断是否形成奇环

            flag=;

        }

    }

    for(i=;i<n;i++)//判断是否联通所有的节点

        if(visited[i]==)

            return ;

    return flag;

}

int main()

{

    int i,j,T,t1,t2;

    scanf("%d",&T);

    for(j=;j<=T;j++)

    {

        scanf("%d%d%d",&n,&m,&s);

        for(i=;i<n;i++)

            edge[i].clear();

        for(i=;i<m;i++)

        {

            scanf("%d%d",&t1,&t2);

            edge[t1].push_back(t2);

            edge[t2].push_back(t1);

        }

        if(solve()==)

            printf("Case %d: YES\n",j);

        else

            printf("Case %d: NO\n",j);

    }

    return ;

}