Leetcode 886) Possible Bipartition

26 Oct 2021 in Algorithms

My Answer

class Solution {
    Map<Integer,ArrayList> neighbors;
    boolean[] visited ;
    int[] teamInfo;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        visited = new boolean[n+1];
        teamInfo = new int[n+1];

        //Creating adjacency list
        neighbors = new HashMap<>();
        for(int[] dislike : dislikes){
            int x = dislike[0];
            int y = dislike[1];
            if(neighbors.containsKey(x)){
                neighbors.get(x).add(y);
            }else{
                ArrayList<Integer> a = new ArrayList<>();
                a.add(y);
                neighbors.put(x,a);
            }
            if(neighbors.containsKey(y)){
                neighbors.get(y).add(x);
            }else{
                ArrayList<Integer> a = new ArrayList<>();
                a.add(x);
                neighbors.put(y,a);
            }

        }
        //iterate neighbors, and mark team
        for(int i=1;i<n+1;i++){
            if(!visited[i]){
                if(!dfs(i,1)){
                    return false;
                }
            }
        }
        return true;
    }
    /*
    {1=[2, 3], 2=[1, 3], 3=[1, 2]}
     visited= [f,t,t,t]
     teamInfo = [0,1,-1,1]
    */
    public boolean dfs(int ind,int team){
        //Base case
        if(teamInfo[ind]==0){
            //set team, and explore 
            teamInfo[ind]=team;
        }else{
            //check if team info is no contraction with previous one
            if(teamInfo[ind]!=team){
                return false;
            }
        }
        if(visited[ind]){
            return true;
        }
        visited[ind]=true;

        //explore team
        if(neighbors.containsKey(ind)){
            ArrayList<Integer> tmp = neighbors.get(ind);
            for(int i :tmp){
                if(!dfs(i,-team)){
                    return false;

                }
            }
        }

        return true;
    }
}

Other Answer

• This made adjacency listlby Array of ArrayLists

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer> l[]=new LinkedList[n+1];
        for(int i=0; i<=n; i++)
            l[i]=new LinkedList<>();
        
        for(int i[]:dislikes){
            l[i[0]].add(i[1]);
            l[i[1]].add(i[0]);
        }
        
        int color[]=new int[n+1];
        Arrays.fill(color, -1);
        
        Queue<Integer> q=new LinkedList<>();
        
        for(int i=1; i<=n; i++){
            
            if(color[i]==-1){
                color[i]=1;
                q.add(i);
            }
            
            while(!q.isEmpty()){
                int src=q.poll();
                int c=color[src];
                
                for(int j:l[src]){
                    if(color[j]==-1){
                        color[j]=1-c;
                        q.add(j);
                    } else if(color[j]==c)
                        return false;
                }
            }
        }
        return true;
    }
}