HDU 5348 MZL's endless loop

乱搞题…第一直觉是混合图的欧拉通路，但是感觉并没有多大关系。最终AC的做法是不断的寻找欧拉通路，然后给边标号。所有边访问了一遍，所有点访问了一遍，效率是o(n+m)。不存在-1的情况。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;const int maxn=;
int n,m;
struct Edge
{
    int from,to;
    int ans;
    int flag;
} edge[*maxn+];
vector<int> G[maxn+];
int tot[maxn+];
int Ru[maxn+];
int Ch[maxn+];
int St[maxn+];void dfs(int now,int x)
{
    for(int i=St[now]; i<G[now].size(); i++)
    {
        Edge &e=edge[G[now][i]];
        if(!e.flag)//这条边没走过
        {
            St[now]=i+;
            if(x==)
            {
                if(e.from==now)
                {
                    e.ans=;
                    e.flag=;
                    tot[e.from]--;
                    tot[e.to]--;
                    Ch[e.from]++;
                    Ru[e.to]++;
                    dfs(e.to,x);
                    return;                }
                else if(e.to==now)
                {
                    e.ans=;
                    e.flag=;
                    tot[e.from]--;
                    tot[e.to]--;
                    Ch[e.to]++;
                    Ru[e.from]++;
                    dfs(e.from,x);
                    return;
                }
            }
            else if(x==)
            {
                if(e.to==now)
                {
                    e.ans=;
                    e.flag=;
                    tot[e.from]--;
                    tot[e.to]--;
                    Ru[e.to]++;
                    Ch[e.from]++;
                    dfs(e.from,x);
                    return;
                }
                else if(e.from==now)
                {
                    e.ans=;
                    e.flag=;
                    tot[e.from]--;
                    tot[e.to]--;
                    Ru[e.from]++;
                    Ch[e.to]++;
                    dfs(e.to,x);
                    return;
                }
            }
        }
    }
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int y=; y<=T; y++)
    {
        scanf("%d%d",&n,&m);
        for(int i=; i<=n; i++) G[i].clear();
        memset(tot,,sizeof(tot));
        memset(Ru,,sizeof(Ru));
        memset(Ch,,sizeof(Ch));
        memset(St,,sizeof(St));
        for(int i=; i<=m; i++)
        {
            scanf("%d%d",&edge[i].from,&edge[i].to);
            if(edge[i].from==edge[i].to)
            {
                edge[i].ans=;
                continue;
            }
            edge[i].flag=;
            G[edge[i].from].push_back(i);
            G[edge[i].to].push_back(i);
            tot[edge[i].from]++;
            tot[edge[i].to]++;
        }
        for(int i=; i<=n; i++)
        {
            while(tot[i])
            {
                if(Ru[i]>=Ch[i]) dfs(i,);
                else dfs(i,);
            }
        }
        for(int i=; i<=m; i++)
            printf("%d\n",edge[i].ans);
    }
    return ;
}