pqpq123's blog

Directed Graph | Largest Connected Component

By pqpq123, history, 4 hours ago, In English

There is a graph (might have cycles) in the form of an adjacency list. How can we find the 'size' of the largest connected component?

Example: 0: 1 2 1: 2: 1 3 3: 1 2 4 4: 2 3

Answer: 5 Reason: We start from 0 and go to 1 and 2, from 2 we can reach 3, from 3 we can reach 4.

What can be the most efficient way to calculate this?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

You can traverse the graph with DFS, and keep track of the visited nodes. For each node, you start DFS if it's not visited. Then you increment your size counter each time you discover a new neighbor and set it to visited, and you take the max size. It's O(n) I believe

→ Reply
»
68 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

you can do DSU that stores the lengths of each component

→ Reply