hdu 5348 MZL's endless loop 2015多校合同訓練試合5リング探し+dfs

MZL's endless loop
Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1837    Accepted Submission(s): 395 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 
|out degree − in degree|≤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 
ui  and 
vi , which describe an edge of the graph.
T≤100 , 
1≤n≤105 , 
1≤m≤3∗105 , 
∑n≤2∗105 , 
∑m≤7∗105 .
 
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 
ui→vi , 
0  for 
ui←vi .
 
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
   
   
   
   

テーマ:無方向の辺を有方向の辺に変えて、各点の出度の入度はただ差が1に等しいだけです
:リングを探し出して、1つのリングの上で、各点の入度=出度
:森が残っていて、森の中でdfsは各結点の出度と入度が1差しかないことを保証します.きっと答えがある
http://blog.sina.com.cn/s/blog_15139 f 1 a 10102 vokk.html解題報告

#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
struct Node{
    int u,v,id,f;
};
#define maxn 100007
vector<Node>head[maxn];
vector<Node>edge;

int in[maxn],out[maxn],check[maxn*5],result[maxn*5];
int cnt = 0;
vector<Node>stack;
int dfn[maxn];
int olar(int u,int dep){
    Node p,q;
    dfn[u] = dep;
    while(head[u].size() > 0){
        p = head[u][head[u].size()-1];
        head[u].pop_back();

        if(check[p.id]) continue;
        check[p.id] = 1;

        stack.push_back(p);
        if(dfn[p.v] != -1 ) {
            dfn[u] = -1;
            return p.v;
        }

        int v = olar(p.v,dep+1);

        if( v != 0){
            if( v == u){
                for(int i = dep;i < stack.size(); i++){
                    q = stack[i];
                    result[q.id] = q.f;
                }
                while(stack.size() > dep)
                    stack.pop_back();
            }
            else {
                dfn[u] = -1;
                return v;
            }
        }
        else stack.pop_back();
    }
    dfn[u] = -1;
    return 0;
}

void dfs(int u){
    int v;
    Node p;
    while(head[u].size() > 0){
        p = head[u][head[u].size()-1];
        head[u].pop_back();
        if(check[p.id]) continue;

        check[p.id] = 1;

        if(out[u] > in[u]){
            in[u]++;
            out[p.v]++;
            result[p.id] = p.f;
        }
        else {
            out[u]++;
            in[p.v]++;
            result[p.id] = !p.f;
        }
        dfs(p.v);
    }
}

int main(){
    int t,n,m;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n; i++)
            in[i] = out[i] = 0, dfn[i] = -1;

        for(int i = 0;i < m; i++)
            check[i] = 0,result[i] = -1;

        Node p;
        edge.clear();
        for(int i = 1;i <= n; i++)
            head[i].clear();

        for(int i = 0;i < m; i++){
            scanf("%d%d",&p.u,&p.v);
            p.f = 1;
            p.id = i;
            edge.push_back(p);
            if(p.u == p.v){
                result[p.id] = 1;
                continue;
            }

            head[p.u].push_back(p);

            swap(p.u,p.v);
            p.f = 0;
            head[p.u].push_back(p);
        }

        for(int i = 1;i <= n; i++)
            if(head[i].size() > 0)
                olar(i,0);
        //cout<<"x"<<endl;
        for(int i = 0;i < m; i++){
            if(result[i] == -1){
                p = edge[i];
                head[p.u].push_back(p);
                swap(p.u,p.v);
                p.f = 0;
                head[p.u].push_back(p);
            }
            check[i] = 0;
        }

        for(int i = 1;i <= n; i++)
            if(head[i].size() > 0) {
                dfs(i);
            }

        int ans = 1;
//cout<<cnt<<endl;
        for(int i = 1;i <= n; i++)
            if(in[i] > out[i] +1 || in[i] + 1 < out[i])
                ans = -1;
        if(ans == -1){
            printf("-1
");
        }
        else
            for(int i = 0;i < m; i++)
                printf("%d
",result[i]);
    }
    return 0;
}
/*

55

4 20
1 1
2 2
3 3
4 4
1 2
1 2
1 2
1 2
2 3
2 3
2 3
2 3
3 4
3 4
3 4
3 4
4 1
4 1
4 1
4 1

3 3
1 2
2 3
3 1

7 6
1 2
1 3
1 4
1 5
1 6
1 7
*/