MZL's endless loop（欧拉路径）

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|≤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 ith line contains a integer 1 or 0, 1 for direct the ith 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

一个欧拉路径的题目。

主要运用知识，一个图中移动有偶数个奇度数的点，所以，可以说，一个图有多条欧拉路径组成。那么可以给边赋值方向。

欧拉回路全是偶度数节点，0个奇度数节点。方向顺着给就行。

代码：

#include using namespace std;#define ll long longconst int maxn =1e5+10;const int INF=0x3f3f3f3f;int d[maxn];struct poin{ int to,next; int id;}edge[maxn*6];int head[maxn],cnt;int n,m;void init(){ cnt=0; memset(head,-1,sizeof(head));}void add(int u,int v){ edge[cnt].to=v; edge[cnt].next=head[u]; edge[cnt].id=0; head[u]=cnt++;}bool dfs(int u){ int v,id; for(int &i=head[u];~i;i=edge[i].next) { v=edge[i].to; id=edge[i].id^edge[i^1].id; if(id)continue; edge[i].id=1; if(d[v]) { d[v]=0; return true; } if(dfs(v))return true; } return false;}int main(){ int t,u,v; scanf("%d",&t); while(t--) { init(); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); d[u]^=1; d[v]^=1; add(u,v); add(v,u); } for(int i=1;i<=n;i++) { if(d[i]) { d[i]=0; dfs(i); } } for(int i = 1; i <= n; i++) while(~head[i]) dfs(i); for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。