csu1356 ：判断一个环是否为奇数环

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1356

题意：给出一个起始点，一些边，有人从这个起始点开始随意走，问在某一个时候，它是否可以处于任意位置。

思路：思考下，就可以明白，只要是一个联通图，并且存在奇数点形成的环，那么在某一个时候就可以处于任意位置。

如何判断存在一个奇数点形成的环？

染色法：就是给每个点进行标号，标为-1，1如果存在一条边连接的两个点标号相同，那么就是存在一个奇数环......

代码：

#include<cstdio> 
#include<cstring> 
#include<iostream> 
#include<algorithm> 
#include<math.h> 
#include<vector> 
using namespace std; 
  
vector<int > g[100002]; 
int vis[100002],ans; 
  
void find1(int u,int x,int f) 
{ 
    if(vis[u]!=-1) 
    { 
        if(vis[u]!=x) 
            ans=1; 
        return ; 
    } 
    if(ans) 
        return ; 
    vis[u]=x; 
    for(int i=0;i<g[u].size();i++) 
    { 
        int v; 
        v=g[u][i]; 
        if(v!=f) 
            find1(v,!x,u); 
    } 
  
} 
int main() 
{ 
    int t,n,m,s,i,a,b,p=1; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%d%d%d",&n,&m,&s); 
        for(i=0;i<=n;i++) 
            g[i].clear(); 
        for(i=0;i<m;i++) 
        { 
            scanf("%d%d",&a,&b); 
            g[a].push_back(b); 
            g[b].push_back(a); 
        } 
        memset(vis,-1,sizeof(vis)); 
        ans=0; 
        find1(s,0,-1); 
        if(ans) 
            printf("Case %d: YES
",p++); 
        else printf("Case %d: NO
",p++); 
    } 
    return 0; 
}