hdu 5348 MZL's endless loop (欧拉路径)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5348

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     Sample Output   1 1 1 0 1 0 1 0 1

给出一个无向图(有环，有重边)，包含n个顶点，m条边，问能否给m条边指定方向，使每个顶点都满足abs(出度-入度)<2。如果能输出任意一种合法方案。

#include 
#include 
#include 
#include 
#pragma comment (linker, "/STACK:102400000,102400000")
using namespace std;const int maxn = 100005;
struct node
{int to, next, id;
}edge[maxn * 6];
int head[maxn], du[2][maxn], sum[maxn];
int vis[maxn * 6], ans[maxn * 6], tot;void init()
{tot = 0;memset(head, -1, sizeof(head));memset(du, 0, sizeof(du));  //du[0][i]i点的入度，du[1][i]i的出度memset(sum, 0, sizeof(sum)); // sum[i]i的度数总和memset(vis, 0, sizeof(vis));memset(ans, -1, sizeof(ans));
}
void addedge(int from, int to, int id)
{edge[tot].to = to;edge[tot].id = id;edge[tot].next = head[from];head[from] = tot++;
}
void dfs(int u, int y)
{for (int i = head[u]; i != -1; i = edge[i].next){if (vis[i]){//当前边已经被访问过head[u] = edge[i].next;  //删边continue;}int v = edge[i].to;if (v != u && du[y][v] < du[y ^ 1][v])  //当前点若和u相连，abs(出度-入度)>1{continue;}vis[i] = vis[i ^ 1] = 1;if (i % 2)   //i是偶数，代表u->v{ans[i / 2] = y ^ 1;}else{ans[i / 2] = y;}du[y][u] ++;du[y ^ 1][v] ++;head[u] = edge[i].next;dfs(v, y);break;}
}
int main()
{//freopen("C://input.txt", "r", stdin);int t, n, m;scanf("%d", &t);while (t--){scanf("%d %d", &n, &m);init();for (int i = 0; i

 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！