[hdu5348]图上找环，删环

http://acm.hdu.edu.cn/showproblem.php?pid=5348

题意：给一个无向图，现在要将其变成有向图，使得每一个顶点的|出度-入度|<=1

思路：分为两步，（1）从图上找环，将环上边的方向设为一致，这样直到图中不存在环，最后剩下一个森林（2）对每一棵树的边进行编号，方法是从根节点向下，对每个点，将其与第一个儿子之间的边设置为与父亲之间的边“互补”的方向，而与儿子之间边的方向则交替分配，显然无论儿子多少个，这个点的出度与入度之差不会超过1。这样两步完成后，所有边都有了方向，所以对任意图都是有解的。自环和重边不需要特殊对待。

无向图上找环：由于是无向图上任意找环，所以存在这样的性质：如果此时此刻从当前边出发找不到环，那么以后再访问这条边时，也同样找不到环，也就是说如果这条边在某个环上，那么现在就可以找到，所以对同一条边访问一次即可。注意代码里面遍历边时，用一个数组表示这个点边集合的入口，一边遍历一边改变入口，这样下次到这个点时，就跳过了以前访问过的从这个点出发的边。

至于删环，用数组标记下即可。

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
#define X                   first
#define Y                   second
#define pb                  push_back
#define mp                  make_pair
#define all(a)              (a).begin(), (a).end()
#define fillchar(a, x)      memset(a, x, sizeof(a))
 
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
 
#ifndef ONLINE_JUDGE
void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);}
void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R>
void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1;
while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T>
void print(const T t){cout<<t<<endl;}template<typename F,typename...R>
void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T>
void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;}
#endif
template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);}
template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);}
template<typename T>
void V2A(T a[],const vector<T>&b){for(int i=0;i<b.size();i++)a[i]=b[i];}
template<typename T>
void A2V(vector<T>&a,const T b[]){for(int i=0;i<a.size();i++)a[i]=b[i];}
 
const double PI = acos(-1.0);
const int INF = 1e9 + 7;
 
/* -------------------------------------------------------------------------------- */
 
const int maxn = 1e5 + 7;
 
 
pii E[maxn * 6];
int SZ;
int Next[maxn * 6];
int last[maxn];
 
int n;
bool ans[maxn * 6], markE[maxn * 6], dif[maxn], flag[maxn], vis[maxn];
int mark[maxn];
 
void add(int u, int v) {
    E[SZ ++] = mp(u, v);
    E[SZ ++] = mp(v, u);
    Next[SZ - 2] = last[u];
    last[u] = SZ - 2;
    Next[SZ - 1] = last[v];
    last[v] = SZ - 1;
}
stack<int> S;
bool now = 0;
void DeleteRing(int u) {
    if (flag[u]) {
        while (S.top() != u) {
            flag[S.top()] = false;
            S.pop();
        }
        now = true;
        return ;
    }
    S.push(u);
    flag[u] = true;
    for (int &i = mark[u]; ~i; i = Next[i]) {
        int id = i;
        pii &e = E[id];
        if (!vis[e.Y] && !markE[id]) {
            markE[id] = true;
            markE[id ^ 1] = true;
            ans[id] = true;
            DeleteRing(e.Y);
            if (S.top() != u) return ;
            if (now) {
                now = false;
                continue;
            }
            markE[id] = false;
            markE[id ^ 1] = false;
            ans[id] = false;
        }
    }
    S.pop();
    flag[u] = false;
    vis[u] = true;
}
 
void dfs(int u) {
    vis[u] = true;
    for (int i = last[u]; ~i; i = Next[i]) {
        int id = i;
        pii &e = E[id];
        if (!vis[e.Y] && !markE[id]) {
            markE[id] = true;
            markE[id ^ 1] = true;
            ans[id ^ dif[u]] = true;
            dif[e.Y] = dif[u];
            dif[u] ^= 1;
            dfs(e.Y);
        }
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    int T, u, v, m;
    cin >> T;
    while (T --) {
        cin >> n >> m;
        SZ = 0;
        fillchar(last, -1);
        fillchar(Next, -1);
        fillchar(ans, 0);
        fillchar(vis, 0);
        fillchar(markE, 0);
        for (int i = 0; i < m; i ++) {
            scanf("%d%d", &u, &v);
            add(u, v);
        }
        for (int i = 1; i <= n; i ++) mark[i] = last[i];
        for (int i = 1; i <= n; i ++) {
            if (!vis[i]) DeleteRing(i);
        }
        fillchar(vis, 0);
        fillchar(dif, 0);
 
        for (int i = 1; i <= n; i ++) {
            if (!vis[i]) dfs(i);
        }
        for (int i = 0; i < SZ; i += 2) {
            printf("%d
", ans[i]);
        }
    }
    return 0;
}