CODEWITHSUNDEEP
pythongraph
user3353391
user3353391

Reputation: 139

Number of Connected component in undirected graph

I'm very confused on how to solve this problem using Python. Please do NOT solve it for me as I'm learning Python and getting full soultions won't help. Say that I have the follwing input:

1
0,4
3
2
1

Where the first line is node 0 and the second line is node 1 etc... (5 nodes in this example). The answer to this program should be "2" as there are 2 "islands" of connected component. one is 2-3 and the second one is 0-1-4. Any tips on how to compute this answer from the given input above would be much appreciated. Thanks! BTW, I'm an 11th grade student so my knowledge of coding is limited, go ez on me :)

Upvotes: 1

Views: 450

Answers (1)

Alfe
Alfe

Reputation: 59436

  1. Read the ASCII-based representation of the graph into a decent Python structure (a dict of node → list_of_edges would do fine for small graphs).
  2. Perform a flooding algorithm on the first unvisited node (visit every node reachable from there).
  3. Continue with step 2 and count how often you find a still-unvisited node.

This terminates when you find no unvisited node anymore.

Upvotes: 1

Related Questions