Directing Edges Unofficial Editorial

general
, ,
1

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