pqpq123's blog

Directed Graph | Largest Connected Component

By pqpq123, history, 8 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

»
7 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
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

you can do DSU that stores the lengths of each component

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

This is a standard problem. What you are referring to is, in the case of a directed graph, the notion of a "strongly connected component". There are a bunch of algorithms that do this such as Trajan's algo. You can find blogs discussing it on cp-algorithms and usaco.guide

→ Reply