MZL’s endless loop

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 131072/131072 K
(Java/Others)
Total Submission(s): 1370 Accepted Submission(s): 297
Special Judge

Problem Description

As we all kown, MZL hates the endless loop deeply, and he commands you to
solve this problem to end the loop.
You are given an undirected graph with n vertexs and m edges. Please
direct all the edges so that for every vertex in the graph the inequation |
o u t d e g r e e − i n d e g r e e | ≤ 1 is satisified.
The graph you are given maybe contains self loops or multiple edges.

Input

The first line of the input is a single integer T , indicating the number of
testcases.
For each test case, the first line contains two integers n and m .
And the next m lines, each line contains two integers u i and v i ,
which describe an edge of the graph.
T ≤ 100 , 1 ≤ n ≤ 10 5 , 1 ≤ m ≤ 3 ∗ 10 5 , ∑ n ≤ 2 ∗
10 5 , ∑ m ≤ 7 ∗ 10 5 .

Output

For each test case, if there is no solution, print a single line with − 1 ,
otherwise output m lines,.
In i th line contains a integer 1 or 0 , 1 for direct the i th edge
to u i → v i , 0 for u i ← v i .

Sample Input

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

Sample Output

1 1 1 0 1 0 1 0 1

题意：给你一个无向图，问你是否能把图变为有向图，且满足每个点的出度与入度的差小于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;
}