HDU5348——DFS——MZL's endless loop

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 $|out~degree~-~in~degree|leq 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.
$Tleq 100$, $1leq nleq 10^5$, $1leq mleq 3*10^5$, $sum nleq 2*10^5$, $sum mleq 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 ightarrow v_i$, $0$ for $u_ileftarrow 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

Source

2015 Multi-University Training Contest 5

详情见博文http://www.cnblogs.com/alihenaixiao/p/4704074.html

/************************************************
Author        :powatr
Created Time  :2015-8-6 19:51:08
File Name     :b.cpp
************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
#pragma comment (linker, "/STACK:102400000,102400000");
using namespace std;
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int MAX = 1e5 + 10;
const int MAXN = 7e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

int head[MAX];
int du[2][MAX];
int sum[MAX];
int vis[MAXN], ans[MAXN];
int n, m, E, u, v;
struct edge{
    int u, v;
    int next;
}a[MAXN];

void inti()
{
    E = 0;
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
    memset(sum , 0, sizeof(sum));
    memset(du, 0, sizeof(du));
    memset(ans, 0, sizeof(ans));
}

void add(int u, int v)
{
    a[E].u = u;
    a[E].v = v;
    a[E].next = head[u];
    head[u] = E++;
}

void dfs(int u, int y)
{
    for(int i = head[u]; ~i; i = a[i].next){
        if(vis[i]) {
            head[u] = a[i].next;
            //访问过就删去
            continue;
        }
        int v = a[i].v;
        if(v!=u && du[y][v] < du[y^1][v]) continue;
        vis[i] = vis[i^1] = 1;
        if(i%2) ans[i/2] =  y^1;//表示从u到v
        else ans[i/2] = y;
        du[y][u]++;
        du[y^1][v]++;
        head[u] = a[i].next;
        dfs(v,y);
        return;
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        inti();
        for(int i = 1 ; i <= m; i++){
            scanf("%d%d", &u, &v);
            add(u, v);
            add(v, u);
            sum[v]++;
            sum[u]++;
        }
        for(int i = 1; i <= n; i++){
            while(du[0][i] + du[1][i] < sum[i]){
                if(du[0][i] <= du[1][i]) dfs(i, 0);
                else dfs(i, 1);
            }
        }
        for(int i = 0 ; i < m; i++)
            printf("%d
", ans[i]);
    }
    return 0;
}

HDU5348——DFS——MZL's endless loop

相关推荐