FillMTR Solution not passing with DSU

data
disjoint-set
fillmtr
find
sept17
structure
union

#1

My following code is giving wrong answer constantly. Please help me. I have used approach of DSU and assigning color to root and comparing color of root while union. If anyone got Ac, with this approach,Please give link of code.

import java.io.;
import java.math.
;
import java.util.*;

import static java.util.Arrays.fill;
import static java.lang.Math.*;
import static java.util.Arrays.sort;
import static java.util.Collections.sort;

class FillTheMatrix
{

public static int mod = 1000000007;
static FasterScanner in = new FasterScanner();
static PrintWriter out = new PrintWriter(System.out);
static int maxn=(int) (1e5+2);
static int[] parent=new int[maxn];
static int[] size=new int[maxn];
static int[] color=new int[maxn];
public static int findheadof(int x)
{
	while(x!=parent[x])
	{
		parent[x]=parent[parent[x]];
		x=parent[x];
	}
	return x;
}
public static void union(int u,int v)
{
	int x=findheadof(u);
	int y=findheadof(v);
	if(x==y)
		return;
	if(size[x]<size[y])
	{
		int temp=x;
		x=y;
		y=temp;
	}
	size[x]+=size[y];
	parent[y]=x;
}
public static void main(String[] args) 
{

	int testcases=in.nextInt();
	while(testcases-->0)
	{
		int n=in.nextInt();
		int q=in.nextInt();
		for(int i=1;i<=n;i++)
		{
			parent*=i;
			size*=1;
			color*=2;
			//color ==2  means no color
		}
		boolean ispossible=true;
		while(q-->0)
		{
			int u=in.nextInt();
			int v=in.nextInt();
			int w=in.nextInt();
			if(u==v)
			{
				if(w!=0)
					ispossible=false;
				continue;
			}
			if(w==0)
			{
				if(color[findheadof(u)]!=2 && color[findheadof(v)]!=2)
				{
					if(color[findheadof(u)]!=color[findheadof(v)])
						ispossible=false;
				}
				if(color[findheadof(u)]==2 && color[findheadof(v)]==2)
				{
					union(u, v);
					color=0;
					color[v]=0;
					continue;
				}
				if(findheadof(u)==u && size[findheadof(u)]==1)
				{
					union(u, v);
					color=color[findheadof(v)];
					continue;
				}
				if(findheadof(v)==v && size[findheadof(v)]==1)
				{
					union(u, v);
					color[v]=color[findheadof(u)];
				}
			}
			else
			{
				if(color[findheadof(u)]!=2 && color[findheadof(v)]!=2)
				{
					if(color[findheadof(u)]==color[findheadof(v)])
						ispossible=false;
				}
				if(color[findheadof(u)]==2 && color[findheadof(v)]==2)
				{
					color[findheadof(v)]=1;
				}
				if(findheadof(u)==u && size[findheadof(u)]==1 && color[findheadof(u)]==2)
				{
					color=1-color[findheadof(v)];
					continue;
				}
				if(findheadof(v)==v && size[findheadof(v)]==1)
				{
					color[v]=1-color[findheadof(u)];
				}
			}
		}
		if(ispossible)
			out.println("yes");
		else
			out.println("no");
	}
	out.close();

}

public static long pow(long x, long n, long mod) 
{
	long res = 1;
	for (long p = x; n > 0; n >>= 1, p = (p * p) % mod)
	{
		if ((n & 1) != 0) 
		{
			res = (res * p % mod);
		}
	}
	return res;
}

public static long gcd(long n1, long n2) 
{
	long r;
	while (n2 != 0) 
	{
		r = n1 % n2;
		n1 = n2;
		n2 = r;
	}
	return n1;
}

static class FasterScanner 
{
	private byte[] buf = new byte[1024];
	private int curChar;
	private int snumChars;

	public int read() 
	{
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try 
			{
				snumChars = System.in.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public String nextLine() 
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do 
		{
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public String nextString() 
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do
		{
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public long nextLong()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do
		{
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int nextInt()
	{
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do 
		{
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n)
	{
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
		{
			arr* = nextInt();
		}
		return arr;
	}

	public long[] nextLongArray(int n) 
	{
		long[] arr = new long[n];
		for (int i = 0; i < n; i++)
		{
			arr* = nextLong();
		}
		return arr;
	}

	private boolean isSpaceChar(int c) 
	{
		return c == ' ' || c == '

’ || c == ‘\r’ || c == ’ ’ || c == -1;
}

	private boolean isEndOfLine(int c)
	{
		return c == '

’ || c == ‘\r’ || c == -1;
}
}

}


#2

I used DSU and colour too in order to solve it. Here’s the link to my AC : link.
But I used the property of 2 colour(i.e. Suppose the colour of set S_1 is white, colour of S_2 must be black and so on).
I know I am bad at explaining. Hope you get it!! Also I learned this from this video!


#3

Can u explain your code? What is the purpose of bfs?


#4

Consider disjoint sets S_1 as {a,b,c} , S_2 as {x,y,z} and S_3 as {p,q,r}.

How did I partition this disjoint sets?

The nodes having difference 0 are clubbed into a set. Hence, nodes of S_1 have 0 difference in value and similarly for S_2 and S_3.

Now, what bfs(probably it is dfs but I mistakenly wrote it as bfs :P) does is that it colours all elements of set with same colour.
For example, if you pass a and white in bfs function, it will set all elements of Set S_1 to white because obviously their colours must be same.
Hope this clears your doubt!