hdu 5215 Cycle(交叉染色法判断无向图的奇偶环)

hdu 5215

思路:询问一个无向图,是否存在奇数环,以及是否存在偶数环。(不同的环之间可以由相同的点,不能有相同的边)

思路:一开始的想法是,根据染色的奇偶性,如果染色到某个之前染色过的点,和当前要染的颜色相同,说明存在奇数环,不同,说明存在偶数环。

感觉很有道理的做法。。。然而错了。。。发现是忽略了上面说的,不同的环之间由相同的点的情况。

比如这组数据:

5 6

1 2

2 3

3 1

1 4

4 5

5 1

两个三元环扣在一起。

实际上是既有奇数环,又有偶数环的。

但是按照我的做法,由于每次只去染没有染过的点,无法发现偶数环。

因此正解是增加一步回溯,这样使得之前存在与某个环中的点还可以出现在其他环中。

然而这样复杂度会炸。。。

于是我们根据,每条边只能走一次,对边加一个vis,使得每条边只走一次,从而保证复杂度。

好题!

这道题我看到了三种解法,第一种是官方解法,tarjan什么(没仔细看)。

第二种是交叉染色。

但是我们可以发现,在这样的情况下,偶环是否和奇环是有联系的,即能不能根据两个奇环的关系,来判断偶环是否存在。

做法:判断是否存在一个点,同时属于两个奇环,如果存在,那么这两个奇环一定可以构成偶环。

证明:令两个奇环分别有x1、x2条边,如果两个环存在一个公共点,令他们存在y条公共边,则它们合并成的环有x1+x2-2*y条边,一定是偶环。因为题目中限制的是边的通过次数,所以即使像下面这组数据一样y=0,偶环是交叉的,也是符合题意的。

第二种做法

但是代码略长,而且还要记录路径。

第三种做法就是我这里用到的做法。。。感觉很完美。。可以当模板23333

/* ***********************************************
Author :111qqz
Created Time :2016年09月01日 星期四 14时47分32秒
File Name :code/hdu/5215.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec secon
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
const int M=3E5+7;
int n,m;
int col[N];
bool even,odd;
bool vis[N];
int cnt ;
int head[N];
struct Edge
{
    int v;
    int nxt;
    bool vis;
}edge[2*M];  
void addedge( int u,int v)
{
    edge[cnt].v = v;
    edge[cnt].nxt = head[u];
    edge[cnt].vis = false;
    head[u] = cnt;
    cnt++;
}
void dfs( int u,int x,int fa)
{
    col[u] = x;
    for ( int i = head[u] ; i !=-1 ; i = edge[i].nxt)
    {
	int v = edge[i].v;
	if (v==fa) continue;交叉染色法判断无向图的奇偶环
	if (col[v]!=-1)
	{
	    if (col[v]==x) odd = true;
	    else even = true;
	}
	if (!edge[i].vis)
	{
	    edge[i].vis = true;
	    dfs(v,1-x,u);
	}
    }
    col[u] = -1;
}
void solve()
{
    odd = false;
    even = false;
    for ( int i = 1 ; i <= n ; i++){
	if (col[i]==-1) dfs(i,0,-1);
    }
}
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	int T;
	cin>>T;
	while (T--)
	{
	    scanf("%d%d",&n,&m);
	    ms(col,-1);
	    ms(head,-1);
	    cnt = 0 ;
	    for ( int i = 1 ;i <= m ; i++)
	    {
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(u,v);
		addedge(v,u);
	    }
	    solve();
	    if (odd) puts("YES");else puts("NO");
	    if (even) puts("YES");else  puts("NO");
	}
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}