1
$\begingroup$

I am trying to solve the following problem:

Input is $2D$ array of integers, $M$, which corresponds to friendship relations. For example, if $M[1][2]=1$, $1$ and $2$ are friends (assuming symmetry it is also true that $M[2][1]=1$). If $M[2][3]=1$, then $\{1,2,3\}$ is a community. If all other entries are $0$, then $\{0\}$ is a community by itself, $\{4\}$ is a community by itself, etc. One can think of $M$ as representation of a graph with $V$ nodes, and $E$ edges. $M$ is $VxV$ matrix and the entries with value $1$ correspond to edges of an undirected graph. For the above example, the total number of communities is $V-2$.

I need to explain the following:

If we solve the above problem with union and find operations (weighted quick union), it will take $O(E+Vlog(V))$ time, explain.

I wrote the code for this. I am also including weighted union and find algorithm code as well below for completeness (but it is a standard known algorithm I guess). With the way I implement it, it does not look like this algorithm takes O(E+Vlog(V)) time. I need to understand how can this be done in O(E+Vlog(V)) time.

It is said that find operation takes O(log(V)) time because the tree is almost balanced with weighted quick union algorithm.

This is my code: enter image description here

The code for weighted quick union and find (given):

public class WeightedQuickUnion {

int[] parent;   // parent[i] = parent of i  
int[] size;     // size[i] = number of sites in subtree rooted at i
int count;      // number of components

/**
 * Initializes an empty union–find data structure 
 * Each site is initially in its own 
 * component.
 * n is the number of sites
 */
public WeightedQuickUnion(int n) {
    count = n;
    parent = new int[n];
    size = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
}

/**
 * Return the number of components.
 *
 */
public int count() {
    return count;
}

/**
 * return the component identifier for the component containing p.
 * p the integer representing the item
 */
public int find(int p) {
    validate(p);
    while (p != parent[p])
        p = parent[p];
    return p;
}

// validate that p is a valid index
private void validate(int p) {
    int n = parent.length;
    if (p < 0 || p >= n) {
        throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));  
    }
}

/**
 * return true if the the item p and item q are in the same component.
 */
public boolean connected(int p, int q) {
    return find(p) == find(q);
}

/**
 * Merge the component containing p with the 
 * the component containing q.
 */
public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);

    if (rootP == rootQ) return;

    // make smaller root point to larger one
    if (size[rootP] < size[rootQ]) {
        parent[rootP] = rootQ;
        size[rootQ] += size[rootP];
    }
    else {
        parent[rootQ] = rootP;
        size[rootP] += size[rootQ];
    }
    count--;
}
$\endgroup$
0
$\begingroup$

You are using Adjacency matrix representation, instead just maintain a list of pairs of friend (i.e. edge list) and iterate it once.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.