MNWLK - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Kasra Mazaheri

Tester: Arshia

Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Observation, Finding Cycle in graph.

PROBLEM:

Given a graph with N junction and M one-way roads (u_i, v_i), Heinz chooses a start city and then performs the following alternatively.

  • Walk his way from the current junction to another junction using any one-way road leading to that junction from current junction.
  • Moonwalk his way out of his current junction to another junction by a one-way road leading from that junction to his current junction. When Heinz does this, he is actually breaking the law (since he is using the one-way road in the wrong direction), but since he is moonwalking, no one will notice.

Heinz plans to end up in the junction where he started after performing an even number of actions. However, he does not want to use any of the one-way roads more than once in any direction (using a road for both walking and moonwalking is not allowed either). It’s worth noting that Heinz must walk at least one one-way road. Can he achieve this goal? If he can, find a sequence of roads he should use.

QUICK EXPLANATION

  • We can make a bipartite graph with 2*N vertices with undirected edges if for every one-way road (u, v) we add an undirected edge (u, N+v) in our bipartite graph.
  • Solving the original problem is equivalent to finding a cycle in this new bipartite graph. Each cycle has even length in the bipartite graph.
  • We can use BFS, DFS or any cycle finding algorithm to find any cycle in this graph, which starts from any node u such that 1 \leq u \leq N

EXPLANATION

From the statement, if Heinz has currently used x roads, he can use a road properly or moonwalk depending upon parity of x. If x is even, he uses the road normally, otherwise, he moonwalks.

Let us build a new graph with 2*N nodes. For a road (u, v) in original graph, lets add an undirected edge (u, v+N) in our new graph.

Lemma: The original problem is equivalent to finding a cycle in this new graph.
Proof:

  • The resulting graph is bipartite with both partitions having size N, since for each edge (u, N+v) added in this graph, we had 1 \leq u \leq N and N+1 \leq N+v \leq 2*N.
  • Moving from u to N+v in this graph correspond to moving from u to v using one way road (u, v).
  • Moving from N+v to u in this graph correspond to moonwalking over edge (u, v), thus moving from v to u.
  • Since this graph is bipartite, all cycles shall have even length, which follows by the definition of bipartite graphs.
  • For nodes u such that 1 \leq u \leq N, all outgoing edges are to nodes N+v such that N+1 \leq N+v \leq 2*N which implies using one-way road. Now, from node N+v all outgoing edges are to nodes 1 \leq u \leq N which implies moonwalking. Hence, it is guaranteed that we use the road normally and moonwalk alternatively, which is required in the original problem.

Hence, the above claim reduces the problem of finding a cycle in this new bipartite graph.

We can use DFS, BFS to find a cycle in this graph, which may be referred here.

An important point to note here is that, if we find a cycle, the edges are to be printed so that the first edge is used as normal edge, the second edge is used for moonwalking, third edge is used as normal edge and so on. It is quite easy to get a WA missing this.

General idea for finding cycles

Start from an unvisited node and build a parent array, keeping track of ancestors. If a visited array is reached again, we can track the path till the first time the vertex was visited.
The same thing can be implemented by pushing vertices (or edge indices) into the stack and popping them out while printing answers.

TIME COMPLEXITY

Time complexity is O(N) per test case.

SOLUTIONS:

Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 400005;
int n, m, cv, cu, ce, M[N];
pair < int , int > P[N];
vector < pair < int , int > > Adj[N];
void DFS(int v)
{
	M[v] = 1;
	for (auto u : Adj[v])
	    if (u != P[v])
	    {
	        if (M[u.first] == 1)
	            cv = v, cu = u.first, ce = u.second;
	        else if (!M[u.first])
	            P[u.first] = {v, u.second}, DFS(u.first);
	    }
	M[v] = 2;
}
inline void Solve()
{
	cv = cu = ce = 0;
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n + n; i ++)
	    Adj[i].clear(), M[i] = 0, P[i] = {0, 0};
	for (int i = 1; i <= m; i ++)
	{
	    int v, u;
	    scanf("%d%d", &v, &u);
	    Adj[v].push_back({u + n, i});
	    Adj[u + n].push_back({v, i});
	}
	for (int i = 1; i <= n + n; i ++)
	{
	    if (M[i])
	        continue;
	    DFS(i);
	    if (cv && cu)
	    {
	        vector < int > E = {ce};
	        while (cv != cu)
	            E.push_back(P[cv].second), cv = P[cv].first;
	        if (cu > n)
	            E.push_back(ce), E.erase(E.begin());
	        printf(":)\n%d\n", (int)E.size());
	        for (int id : E)
	            printf("%d ", id);
	        printf("\n");
	        return ;
	    }
	}
	printf(":(\n");
	return ;
}
int main()
{
	int q;
	scanf("%d", &q);
	for (; q; q --)
	    Solve();
	return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>

using namespace :: std;


//=======================================================================//
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
	    char g=getchar();
	    if(g=='-'){
	        assert(fi==-1);
	        is_neg=true;
	        continue;
	    }
	    if('0'<=g && g<='9'){
	        x*=10;
	        x+=g-'0';
	        if(cnt==0){
	            fi=g-'0';
	        }
	        cnt++;
	        assert(fi!=0 || cnt==1);
	        assert(fi!=0 || is_neg==false);

	        assert(!(cnt>19 || ( cnt==19 && fi>1) ));
	    } else if(g==endd){
	        assert(cnt>0);
	        if(is_neg){
	            x= -x;
	        }
	        assert(l<=x && x<=r);
	        return x;
	    } else {
	        assert(false);
	    }
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
	    char g=getchar();
	    assert(g!=-1);
	    if(g==endd){
	        break;
	    }
	    cnt++;
	    ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
//=======================================================================//



const ll maxn=4e5+500;

bool vis[maxn];
ll s[maxn];
ll t[maxn];
vector<ll> ans;
vector<ll> ger[maxn];
ll b=-1;

bool dfs(ll a,ll p=-1){
	vis[a]=1;
	for(auto e:ger[a]){
		ll tah=(s[e]^t[e]^a);
		if(e!=p){
			if(vis[tah]){
	            b=tah;
				ans.pb(e);
				return 1;
			}else{
				if(dfs(tah,e)){
					if(b==-2){
	                    return 1;
					}
					ans.pb(e);
					if(a==b){
	                    b=-2;
					}
					return 1;
				}
			}
		}
	}
	return 0;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll q;
	q=readIntLn(1,5);
	while(q --){
	    ll n,m;
	    n=readIntSp(1,(ll)2e5);
	    m=readIntLn(1,(ll)2e5);
	    for(ll i=0;i<m;i++){
	        s[i]=readIntSp(1,n);
	        t[i]=readIntLn(1,n);
	        s[i]--;
	        t[i]--;
	        t[i]+=n;
	        ger[s[i]].pb(i);
	        ger[t[i]].pb(i);
	    }
	    ll ok=0;
	    for(ll i=0;i<2*n;i++){
	        if(!vis[i]){
	            if(dfs(i)){
	                cout<<":)\n"<<ans.size()<<endl;
	                if (t[ans[0]] != t[ans[1]])
	                    ans.push_back(ans[0]), ans.erase(ans.begin());
	                for(auto v:ans){
	                    cout<<v+1<<' ';
	                }
	                cout<<endl;
	                ok=1;
	                break;
	            }
	        }
	    }
	    if(ok==0){
	        cout<<":("<<endl;
	    }
	    for(ll i=0;i<2*n;i++){
	        ger[i].clear();
	        vis[i]=0;
	        ans.clear();
	        b=-1;
	    }
	}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class MNWLK{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni(), m = ni();
	    int[] from = new int[m], to = new int[m];
	    for(int i = 0; i< m; i++){
	        from[i] = ni()-1;
	        to[i] = ni()-1+n;
	    }
	    int[][] g = makeU(2*n, from, to);
	    boolean[] vis = new boolean[2*n];
	    for(int i = 0; i< n; i++){
	        if(vis[i])continue;
	        
	        int end = dfs(g, from, to, vis, i, -1);
	        if(end != -1){
	            int[] ans = new int[m];
	            int c = 0;
	            int last = end;
	            do{
	                int ee = st.pop();
	                ans[c++] = ee;
	                end = from[ee]^to[ee]^end;
	            }while(end != last);
	            if(last > n){
	                int ee = ans[0];
	                for(int j = 0; j< c-1; j++)ans[j] = ans[j+1];
	                ans[c-1] = ee;
	            }
	            pn(":)");
	            pn(c);
	            for(int j = 0; j< c; j++)p(1+ans[j]+" ");pn("");
	            return;
	        }
	    }
	    pn(":(");
	}
	Stack<Integer> st = new Stack<>();
	int dfs(int[][] g, int[] from, int[] to, boolean[] vis, int u, int p) throws Exception{
	    vis[u] = true;
	    for(int e:g[u]){
	        int v = from[e]^to[e]^u;
	        if(v == p)continue;
	        st.add(e);
	        if(vis[v])return v;
	        int nxt = dfs(g, from, to, vis, v, u);
	        if(nxt != -1)return nxt;
	        hold(e == st.pop());
	    }
	    return -1;
	}
	int[][] makeU(int n, int[]from, int[] to){
	    int[][] g = new int[n][];int[] cnt = new int[n];
	    for(int i:from)cnt[i]++;
	    for(int i:to)cnt[i]++;
	    for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
	    for(int i = 0; i< from.length; i++){
	        g[from[i]][--cnt[from[i]]] = i;
	        g[to[i]][--cnt[to[i]]] = i;
	    }
	    return g;
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new MNWLK().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

7 Likes

Wow, elegant solution.

2 Likes

Yes, it is!
Another elegant problem https://www.codechef.com/problems/PWRTREE

2 Likes

What is wrong in my submission? My approach was a modified DFS. Anybody else who used DFS. My submission link https://www.codechef.com/viewsolution/27512351

How do you ensure that you do not use same edge twice? i.e., I move from 1 -> 2 and then back to 2 by 2 -> 1 again?

1 Like

Any intuition behind adding edge (u,v+N),I mean how you transform the problem into cycle finding.
Is there any algorithm used in such type question or it is by practice
Thanks

I pass a (dict/set) of all tuples i,j which can not be visited. If I visit some edge I will append both ways i,j and j,i tuple to this dict. I will not go on these edges again in same dfs path.

1 Like

This solution is awesome. Reading this makes me feel the beauty of CP :slight_smile:
Thanks once again.

I have tried everything and thought of many test cases, my code works well on all those. But still getting segmentation fault on submission. https://www.codechef.com/viewsolution/27517774
Someone please help @taran_1407 .
Thanks in advance.

Pure Practice :slight_smile:

Hi sir @taran_1407 , can you please look at this code. I have implemented your approach only. Not able to find why sigsegv occuring. https://www.codechef.com/viewsolution/27517774

I’m no good in cpp, but usually there’s NZEC due to array index out of bounds, divide by zero. Check array sizes and indices carefully and refer other accepted submissions.

I am trying your code.

I may have misunderstood the question, but is the question essentially this -

Given an undirected graph, find a cycle of even length where every edge is only used once

Can someone please confirm this ?

Can I just say that this is a brilliant problem ? :slight_smile:

I’m back after a month and I finally understood. That is not the original question.

The solution involves an elegant construction where we create a graph consisting of 2N vertices. Now, we just have to find a cycle on this graph. :slight_smile: