The number of connected component 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.


  
  If it's 0, skip
  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.
  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 &lt; ROWS; ++r)
    {
        for(c = 0; c &lt; COLS; ++c)
        {
            if(m[r][c] == 0)
                continue;

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

            if(m[r][c] &gt; 0)
            {
                if(r-1&gt;=0 &amp;&amp; m[r-1][c] == -1)
                    m[r-1][c] = m[r][c];
                if(r+1&lt;ROWS &amp;&amp; m[r+1][c] == -1)
                    m[r+1][c] = m[r][c];
                if(c-1&gt;=0 &amp;&amp; m[r][c-1] == -1)
                    m[r][c-1] = m[r][c];
                if(c+1&lt;COLS &amp;&amp; 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?
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.