Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

pqpq123's blog

Directed Graph | Largest Connected Component

By pqpq123, history, 21 month(s) 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

Comments Comments (2)
| Write comment?
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

you can do DSU that stores the lengths of each component

→ Reply
»
21 month(s) ago, hide # |
 
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