Dynamic Connectivity Problem

Dynamic Connectivity Problem by Quick-Find and Quick-Union 

Dynamic connectivity Problem is a problem in which we have to find there is a connected path or not for a objects.

Note:-

Only gives there is a path or not.For finding the paths there are other algorithms.

Example:-

There are the following 7 objects.

Union commands on two objects which will join that two objects.

Following union command will apply on these objects:-

union(1,3)

union(2,4)

union(6,7)

union(0,1)

union(5,7)

union(4,5)

And then object connectivity will become:-

Now connected commands would work as:-

connected(0,3)         true

connected(2,7)         true

connected(0,2)         false

Applications involve manipulating objects of all types.

・Pixels in a digital photo.

・Computers in a network.

・Friends in a social network.

・Transistors in a computer chip.

・Elements in a mathematical set.

・Variable names in Fortran program.

・Metallic sites in a composite system.

Now to solve this problem the following two approahes are given below:- 

1.Quick-Find
Quick Find is also known as eager approach.
Union
In this approach,we update value in a array(initialize with no. of objects) with the same value.
Example:-
union(3,4)          Then,    id[3]=id[4]  but now we have to update all the value of objects which are connected to Object 3.
And for all x for id[x]=id[3] update id[x]=id[4]. 

Connected
If id of two objects are equal then they are connected.

Java Program:-

/**

 * @(#)QuickFind2.java

 *

 *

 * @author Suyash Bhala

 * @version 1.00 2015/1/27

 */

/*

 *Quick Find(Eager Approach)

 **/

class UF{

private int id[];

public UF(int N){

id=new int[N];

for(int i=0;i<N;i++){

id[i]=i;

}

}

public boolean connected(int p,int q){

return id[p]==id[q];

}

public void union(int p,int q){

int pid=id[p];

int qid=id[q];

for(int i=0;i<id.length;i++){

if(pid==id[i]){

id[i]=qid;

}

}

}

}

public class QuickFind2 {

    public static void main(String args[]){

    UF ob=new UF(8);

    ob.union(1,3);

    ob.union(2,4);

    ob.union(6,7);

    ob.union(0,1);

    ob.union(5,7);

    ob.union(4,5);

    System.out.println("Connected(0,3)=>"+ob.connected(0,3));

    System.out.println("Connected(2,7)=>"+ob.connected(2,7));

    System.out.println("Connected(0,2)=>"+ob.connected(0,2));

    }

}

2.Quick-Union
Quick Union is also known as lazy approach.

Union
To connect the objects(let us say union(p,q)) make p child of q by updating id[p]=q.
But for union of child to another root or vice-versa, update id[root(p)]=id[root(q)]

Connected

If root of two objects are equal then they are connected. 

Java Program:-

/**
 * @(#)QuickUnion.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2015/1/28
 */
/*
 *Quick Union(Lazy Approach)
 **/

class UF{
private int id[];
public UF(int N){
id=new int[N];
for(int i=0;i<N;i++){
id[i]=i;
}
}
public boolean connected(int p,int q){
return root(p)==root(q);
}
private int root(int i){
while(i!=id[i]){
i=id[i];
}
return i;
}
public void union(int p,int q){
int i=root(p);
int j=root(q);
id[i]=j;
}
}

public class QuickUnion {

    public static void main(String args[]){
    UF ob=new UF(8);
    ob.union(1,3);
    ob.union(2,4);
    ob.union(6,7);
    ob.union(0,1);
    ob.union(5,7);
    ob.union(4,5);
    System.out.println("Connected(0,3)=>"+ob.connected(0,3));
    System.out.println("Connected(2,7)=>"+ob.connected(2,7));
    System.out.println("Connected(0,2)=>"+ob.connected(0,2));
    }
 

}

Output:-

Connected(0,3)=>true

Connected(2,7)=>true

Connected(0,2)=>false

Analysis:-

Algorithm      initialize      union        find 

Quick-Find          N                 N              1

Quick-Union       N                 N              N

-------------X---------------X--------------X--------------X--------------X-------------

Problem Broken Necklace

Broken Necklace

You have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random. Here are two examples for n=29:

                1 2                               1 2
            r b b r                           b r r b
          r         b                       b         b
         r           r                     b           r
        r             r                   w             r
       b               r                 w               w
      b                 b               r                 r
      b                 b               b                 b
      b                 b               r                 b
       r               r                 b               r
        b             r                   r             r
         b           r                     r           r
           r       r                         r       b
             r b r                             r r w
            Figure A                         Figure B
                        r red bead
                        b blue bead
                        w white bead

The beads considered first and second in the text that follows have been marked in the picture.
The configuration in Figure A may be represented as a string of b's and r's, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .
Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).
Determine the point where the necklace should be broken so that the most number of beads can be collected.

Example

For example, for the necklace in Figure A, 8 beads can be collected, with the breaking point either between bead 9 and bead 10 or else between bead 24 and bead 25.
In some necklaces, white beads had been included as shown in Figure B above. When collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color. The string that represents this configuration can include any of the three symbols r, b and w.
Write a program to determine the largest number of beads that can be collected from a supplied necklace.

PROGRAM NAME: beads

INPUT FORMAT

Line 1:	N, the number of beads
Line 2:	a string of N characters, each of which is r, b, or w

SAMPLE INPUT (file beads.in)

29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

OUTPUT FORMAT

A single line containing the maximum of number of beads that can be collected from the supplied necklace.

SAMPLE OUTPUT (file beads.out)

11

Program:-

import java.io.*;

class beads {

 public static int find(String str){
  int a[]=new int[str.length()];
  for(int i=0;i<str.length();i++){
   a[i]=count(str,i);
  }
  return max(a);
 }
 public static int max(int a[]){
  int max=a[0];
  for(int i=1;i<a.length;i++){
   if(max<a[i]){
    max=a[i];
   }
  }
  return max;
 }
 
 public static int count(String str,int in){
  int f,b,cnt=0;
  boolean fd=false,bd=false;
  f=in;
  b=in-1;
  if(b<0){
    b=str.length()-1;
  }
  if(f>str.length()-1){
   f=0;
  }
  char ff=str.charAt(f);
  char bf=str.charAt(b);
  while(true){
   if(b<0){
    b=str.length()-1;
   }
   if(f>str.length()-1){
    f=0;
   }
   if((str.charAt(f)==ff||str.charAt(f)=='w'||ff=='k')&&!fd){
    if(ff=='w'){
     ff='k';
    }
    if(ff=='k'&&str.charAt(f)!='w'){
     ff=str.charAt(f);
    }
    cnt++;
   }else{
    fd=true;
   }
   if(cnt==str.length()){
    break;
   }
   
   if((str.charAt(b)==bf||str.charAt(b)=='w'||bf=='k')&&!bd){
    if(bf=='w'){
     bf='k';
    }
    if(bf=='k'&&str.charAt(b)!='w'){
     bf=str.charAt(b);
    }
    cnt++;
   }else{
    bd=true;
   }
   if((fd&&bd)||cnt==str.length()){
    break;
   }
   b--;
   f++;
  }
  return cnt;
 }
    public static void main(String ar[])throws IOException{
     BufferedReader br=new BufferedReader(new FileReader("beads.in"));
     PrintWriter out=new PrintWriter(new FileWriter("beads.out"));
     int len=Integer.parseInt(br.readLine());
     String str=br.readLine();
     out.println(find(str));
     out.close();
     System.exit(0);
    }   
}

-------X-------X-------X-------X-------X-------X-------X-------X---------