s*****n
发帖数: 162 | 1 This is an old G onsite question about one year back.
Find a connection between two people if there is one, or return false.
Everyone has father and mother and the connection means if there are any
common relatives.
My idea is as following:
The relative social network should be represented as graphs instead of
binary trees. One way to solve this problem is to use BFS. Specifically, we
can do BFS for person1 and person2 for their ancestors/descendants
simultaneously. We can use a hashtable to record every ancestor/descendant
that find along the BFS. If a common ancestor/descendant is found or person1
/person2 is found to be person2/person1’s ancestor/descendant, then they
have a connection. If they do not have any common ancestor/descendant, then
return false.
I was wondering if there is any better solution? | l***i
发帖数: 1309 | 2 put an undirected edge from a person to his/her father, and one edge to the
mother. Then two persons are related iff there is a path from one person to
the other. You can do either bfs or dfs assume the graph is small enough.
Basically the connectivity problem. | b*******d
发帖数: 750 | 3 maybe just a common ancestor means there is a connection also? |
|
