Number of components in graph

general
, ,
1

i have been trying to solve this problem lately…


i am trying to find out the total no. of connected components for the given grid…but i am getting wrong answer for that.can someone tell me why am i getting wrong answer ??.and what would be the correct approach for it…
2

I don’t know your approach and I don’t know where to find your submision, so when you want to get check a code, you should paste it here (best way with ideone or similar thing).

But correct (and I think the easiest) way to do this is following. First create graph. In task you have graph oriented, but forget it and make each edge bidirectional. Now as you mentioned, you want to find number of components in this graph.

You can use Depth first search. Basically you want to label each vertex with label ‘visited’ or ‘unvisited’. At the begining all vertices are ‘unvisited’. Now iterate through all vertices. If you process ‘visited’ vertex, just continue. You already count this component. But if the vertex is ‘unvisited’, you want to visit each vertex in this component and add one to result.

So you can use recursive function with parameter vertex v, where we want to start. Now you look through all neighbours of vertex v. If the neighbour w is ‘visited’ you can ignore it, you have been there before. But when is ‘unvisited’ change it to ‘visited’ and call same function with parameter w.

void dfs(int v) {
    visited[v] = true;
    for(w in neighbours of v) {
        if(visited[w] == false) dfs(w);
    }
}

Simple, isn’t it? :slight_smile: Number of iteration in which you call this function dfs() is result.

1 Like
3

You can use union find data structures.They are simple to implement and can give answer in O(n log(n)). Check this http://en.wikipedia.org/wiki/Disjoint-set_data_structure.

This is the same way you check cycles in kruskals minimum spanning tree algo.

You can also try one similar problem http://www.codechef.com/JAN12/problems/RHOUSE/

1 Like
4

@subway >> A greedy approach would result in a better running time. As @NR mentioned, you can use union-find algorithm.

You can read the following http://www.stanford.edu/~ashishg/amdm/handouts/scribed-lec8.pdf

5

@michal27-am doing the same thing.
here is my ideone solution: http://ideone.com/r4kzC4

6

this isn’t necassary to use. It’s more complicated than it should be. Union-find data structure allows you to connect components dynamicly, but you don’t need this here.

Also it’s slower than mine solution and in fact with good implementation it’s not O(n log n) but n times inverse Ackermann function of n.

7

well there are several problems in your solution. Firs, you using edges with direction, but you want bidirectional roads. Suppose this input:

3 4
SWWW
SENN
EEEN

Your answer is 2, but you have got only one component.

Second problems are boundaries. You ask “if(vis[i-1][j]==0) dfs(i-1,j);” But what if i=0. Than vis[-1][j] doesn’t exist what can cause many problems.