×

Directing Edges Unofficial Editorial

First of all you have given a graph with undirected edges.You have to give a direction to each edge such that indegree of all vertices to be even? Question Link

My Approach

Initially i have given all the edges same direction as i am taking input.

for(ll i=0;i<m;i++){
scanf("%d%d",&u,&v);
edges[i] = make_pair(u,v);
direction[make_pair(u,v)] = 1;
direction[make_pair(v,u)] = 0;
graph[u].push_back(v);
graph[v].push_back(u);
coun1[u] = coun1[u] + 1;
}


First of all if number of edges are odd so no possible direction of all edges can make it a graph with even indegree. so if m is odd ans will be -1. while taking input i have made the graph. Then using BFS i have converted into a tree. Any possible tree can be made consisting of all vertices (n) ans n-1 edges. After that i used a set to insert all the nodes having odd indegree.

Euler tour is used to convert a tree into a 1D array. This is used to make indegree even.

bool flag = false;

    for(ll i=0;i<euler_path.size();i++){
if(flag){
ll u = euler_path[i],v = euler_path[i-1];
direction[make_pair(u,v)] = !direction[make_pair(u,v)];
direction[make_pair(v,u)] = !direction[make_pair(v,u)];
}
if(req.find(euler_path[i])!=req.end()){
flag = !flag;
req.erase(euler_path[i]);
}
}


Now reversing all the edges direction in between two nodes with odd indegree will make indegree of all inbetween nodes even as by doing so, indegree of inbetween nodes will remain same of increased by 2 or decreased by 2. HOW???? Just try to make some cases using pen and paper.

And indegree of both nodes with odd indegree will become even.

My Solution

1
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,197
×398
×73

question asked: 18 Dec '18, 17:58

question was seen: 254 times

last updated: 18 Dec '18, 17:58