# FillMTR Solution not passing with DSU

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];
{
while(x!=parent[x])
{
parent[x]=parent[parent[x]];
x=parent[x];
}
return x;
}
public static void union(int u,int 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]=i;
size[i]=1;
color[i]=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)
{
{
ispossible=false;
}
{
union(u, v);
color[u]=0;
color[v]=0;
continue;
}
{
union(u, v);
continue;
}
{
union(u, v);
}
}
else
{
{
ispossible=false;
}
{
}
{
continue;
}
{
}
}
}
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;

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

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

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

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

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

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

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

private boolean isSpaceChar(int c)
{
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

private boolean isEndOfLine(int c)
{
return c == '\n' || c == '\r' || c == -1;
}
}
``````

}

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!

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

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.