Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Post History
Your example is a bipartite graph in adjacency list format. The cars are nodes on the left, the people are nodes on the right. When a person "has" a car, there is an edge between the car and person...
Answer
#1: Initial revision
by
matthewsnyderâ€
·
2023-06-30T00:02:07Z (10 months ago)
Your example is a bipartite graph in adjacency list format. The cars are nodes on the left, the people are nodes on the right. When a person "has" a car, there is an edge between the car and person. Your question is equivalent to asking for the connected components of the graph. This can be done with standard algorithms like Depth First Search in O(n+m) time (nodes+edges). You can find implementations in libraries like NetworkX.