You are not logged in. Please login at www.codechef.com to post your questions!

×

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

asked 18 Dec '18, 17:58

failed_coder's gravatar image

5★failed_coder
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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