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]=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)
{
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[u]=0;
color[v]=0;
continue;
}
if(findheadof(u)==u && size[findheadof(u)]==1)
{
union(u, v);
color[u]=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[u]=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[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;
}
}
}