4
\$\begingroup\$

Compute the number of connected component in a matrix, saying M. Given two items with coordinates [x1, y1] and [x2, y2] in M, if

  • M(x1, y1) == -1 and
  • M(x2, y2) == -1 and
  • |x1-x2| + |y1-y2| == 1

then they are connected.

Example:

-1  0 -1  0  0
-1 -1  0 -1 -1
 0  0  0  0 -1
 0  0  0 -1 -1
 0  0  0 -1  0
 0 -1  0  0  0
 0 -1  0  0  0

Output: 4. And they are:

-1
-1 -1

-1

-1 -1
   -1
-1 -1
-1

-1
-1

My idea is to scan the matrix.

Initialization:
count = 0.

For every item in the matrix, do the following three tests.

  1. If it's 0, skip

  2. If it's -1, check its four neighbors. If there is a neighbor whose value is not 0 and -1, assign the value of this neighbor to the current item. Otherwise, count++, ant then assign count to the current item.

  3. If it's not 0 and -1, assign the value of current item to its four neighbors whose value is -1.

The following is my code:

int num_cc(int m[][COLS])
{
    int count = 0; 
    int r;
    int c;

    for(r = 0; r < ROWS; ++r)
    {
        for(c = 0; c < COLS; ++c)
        {
            if(m[r][c] == 0)
                continue;

            if(m[r][c] == -1)
            {
                if(r-1>=0 && m[r-1][c] > 0)
                    m[r][c] = m[r-1][c];
                else if(r+1<ROWS && m[r+1][c] > 0)
                    m[r][c] = m[r+1][c];
                else if(c-1>=0 && m[r][c-1] > 0)
                    m[r][c] = m[r][c-1];
                else if(c+1<COLS && m[r][c+1] > 0)
                    m[r][c] = m[r][c+1];
                else
                {
                    count++;
                    m[r][c] = count;
                }
            }

            if(m[r][c] > 0)
            {
                if(r-1>=0 && m[r-1][c] == -1)
                    m[r-1][c] = m[r][c];
                if(r+1<ROWS && m[r+1][c] == -1)
                    m[r+1][c] = m[r][c];
                if(c-1>=0 && m[r][c-1] == -1)
                    m[r][c-1] = m[r][c];
                if(c+1<COLS && m[r][c+1] == -1)
                    m[r][c+1] = m[r][c];       
            }

        }
    }

    return count;
}

Can anyone help me verify it? Is it correct? Or is there any other solutions?

\$\endgroup\$
  • \$\begingroup\$ Why is the isolated -1 (item 2 in the output) a component? It isn't connected to anything, assuming that off-the-edge shouldn't count. \$\endgroup\$ – Glenn Rogers Oct 16 '12 at 8:48
  • \$\begingroup\$ @GlennRogers, the diagonal line is not considered as connected. \$\endgroup\$ – Fihop Oct 16 '12 at 13:58
  • 1
    \$\begingroup\$ There is of course a more general solution -en.wikipedia.org/wiki/Connected_component_(graph_theory) -, but you would only need that if you want more than just the number of components. \$\endgroup\$ – Frank Oct 16 '12 at 21:00
  • \$\begingroup\$ @Frank Thanks very much. This is an easier question than the more general connected component problem. We only need to compute the number. And We're able to change the element of the matrix. \$\endgroup\$ – Fihop Oct 16 '12 at 22:16
  • \$\begingroup\$ Please check the following link: en.wikipedia.org/wiki/Connected-component_labeling \$\endgroup\$ – Fihop Oct 17 '12 at 5:48
5
\$\begingroup\$

Style: Depending on coding guidelines and preferences you may want to consider moving the declaration of r and c into the for-loops (for (int r = 0...), as these variables are not supposed to be used outside of the loop, and hence, an outside declaration kind of contradicts this contract.

Correctness: I'm afraid your greedy approach does not work out well - in other words: it gives wrong results. Consider the following matrix (or if you loop the other way round its symmetric variant) :

 0  0  0  0 -1
-1 -1 -1 -1 -1

By going through the first row first, you would create your first connected group with this intermediate result, before the row-loop switches to the second row:

 0  0  0  0  1
-1 -1 -1 -1  1

Next, the inner loop will find another -1 cell with no higher-numbered neighbors and create a second connected component, although there really is only one.

Succinctness: If the code was correct, you might as well eliminate all the if statements in the loop except for the one comparing against -1. The others are redundant in their behavior.

\$\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.