You are not logged in. Please login at www.codechef.com to post your questions!

×

FillMTR Solution not passing with DSU

0
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]=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;
    }
}

}

asked 19 Sep '17, 13:25

parth_patel15's gravatar image

3★parth_patel15
123
accept rate: 0%

edited 19 Sep '17, 13:29


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!

link

answered 19 Sep '17, 14:00

dishant_18's gravatar image

4★dishant_18
61419
accept rate: 12%

edited 19 Sep '17, 14:03

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

(19 Sep '17, 15:27) parth_patel153★

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!

(19 Sep '17, 15:41) dishant_184★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×286
×67
×57
×23
×16
×15
×7

question asked: 19 Sep '17, 13:25

question was seen: 346 times

last updated: 19 Sep '17, 15:42