Thread: Finding the number of connected components

  1. 02-17-2013 #1
    Goku
    Goku is offline
    Registered User
    Join Date
    Feb 2013
    Posts
    7

    Finding the number of connected components

    Hello,

    I can't figure out how to find the number of connected components from an undirected disconnected graph.

    the input I'm getting is like this:
    7
    1 2
    4 5
    3 6
    2 7

    the top number is the number of vertices and the rest of the numbers are the edges, eg. 1--2 is an edge.

    Is there a way that you can implement DFS algorithm to find the number of connected components?     like increment a variable every time DFS is called or something?


    Thanks in advance
  2. 02-18-2013 #2
    Salem
    Salem is offline
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,659
    So what's the intended output of all this?

    Something like
    There are 3 separate components
    1 2 7
    4 5
    3 6

    A first step would be to write the code to just read the input data into some kind of data structure.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
« Previous Thread | Next Thread »
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. code to reverse a 4=digit number+finding if 4 digit number is a palindrome
    By renegadewarrior in forum C Programming
    Replies: 2
    Last Post: 10-31-2009, 06:49 PM
  2. Connected Components not quite working
    By taurus in forum C Programming
    Replies: 1
    Last Post: 09-22-2009, 06:23 PM
  3. Finding The Hcf Of A Number
    By Saimadhav in forum C++ Programming
    Replies: 5
    Last Post: 10-31-2008, 06:50 AM
  4. Storing components of a complex number
    By cashmerelc in forum C Programming
    Replies: 6
    Last Post: 11-19-2007, 01:37 PM
  5. number of components
    By kellymart87 in forum C++ Programming
    Replies: 2
    Last Post: 04-17-2007, 09:26 PM