MZL‘s endless loop

2
3 3
1 2
2 3
3 1
7 6
1 2
1 3
1 4
1 5
1 6
1 7

1
1
1
0
1
0
1
0
1

解法：无向图一定能够满足条件。度数奇数的为欧拉路径的起点或终点。偶数的为欧拉路径中间点，或环上的点。

代码：

#include <stdio.h>  
#include <ctime>  
#include <math.h>  
#include <limits.h>  
#include <complex>  
#include <string>  
#include <functional>  
#include <iterator>  
#include <algorithm>  
#include <vector>  
#include <stack>  
#include <queue>  
#include <set>  
#include <map>  
#include <list>  
#include <bitset>  
#include <sstream>  
#include <iomanip>  
#include <fstream>  
#include <iostream>  
#include <ctime>  
#include <cmath>  
#include <cstring>  
#include <cstdio>  
#include <time.h>  
#include <ctype.h>  
#include <string.h>  
#include <assert.h>  
#pragma comment (linker, "/STACK:102400000,102400000")

using namespace std;

const int MAXN = 1e6+10;
const int MAXM = 1e6+10;

int n, m;
int x, y;

//////////////
struct Edge
{
	int to, next;
	int index;
	bool flag;
}edge[MAXM];

int head[MAXM], tot;
int sum_du[MAXN];//总度数
int du[MAXN][2];//d[i][0] 入度 d[i][1]出度
int ans[MAXM];//答案

void addedge(int u, int v, int index)
{
	edge[tot].to = v;
	edge[tot].flag = false;
	edge[tot].index = index;
	edge[tot].next = head[u];
	head[u] = tot++;
}

void init()
{
	tot = 0;
	memset(head, -1, sizeof(head));
	memset(du, 0, sizeof(du));
	memset(sum_du,0,sizeof(sum_du));
	memset(ans,-1,sizeof(ans));
}
///////////////////

void dfs(int u,int ok)
{
	for (int i = head[u]; i != -1; i = edge[i].next)
	{
		if (edge[i].flag)//访问过的边  删除
		{
			head[u] = edge[i].next;
			continue;
		}
		int v = edge[i].to;
		if (u != v && du[v][ok^1] > du[v][ok])
			continue;
		/////////////
		edge[i].flag = true;
		edge[i ^ 1].flag = true;
		if (i % 2  == 1)
			ans[i / 2] = ok ^ 1;
		else
			ans[i / 2] = ok;

		du[u][ok]++;
		du[v][ok ^ 1]++;
		head[u] = edge[i].next;//删边
		dfs(v,ok);
		break;
	}
}

int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		scanf("%d %d",&n,&m);
		init();
		for (int i = 0; i < m; i++)
		{
			scanf("%d%d",&x,&y);
			addedge(x, y, i);
			addedge(y, x, i);
			sum_du[x]++;
			sum_du[y]++;
		}
		for (int i = 1; i <= n; i++)
		{
			while (du[i][0] + du[i][1] < sum_du[i])
			{
				if (du[i][0] <= du[i][1])
					dfs(i, 0);//正向走
				else
					dfs(i, 1);//反向走
			}
		}
		for (int i = 0; i < m; i++)
			printf("%d\n",ans[i]);
	}
	return 0;
}

hdu 5348 MZL's endless loop

原文：http://blog.csdn.net/u014427196/article/details/47297889