老中面试官,问了个这个题目: Find all connected components in an undirected graph. 我尝试了DFS和BFS,不知道对不对,最后挂了。 大家有啥好解法?
g*7
2 楼
加油。。。。。。。
s*x
3 楼
lintcode上有啊
【在 f**********n 的大作中提到】 : 老中面试官,问了个这个题目: : Find all connected components in an undirected graph. : 我尝试了DFS和BFS,不知道对不对,最后挂了。 : 大家有啥好解法?
h*r
4 楼
I have only 4 calls @0.25 and just support you. I hope I can got some from mu to buy some Hallowen stuff for my kids. If it is not double, I will let it rot away.
【在 g**********7 的大作中提到】 : 加油。。。。。。。
f*n
5 楼
没刷那个,刷了leetcode。。。
【在 s********x 的大作中提到】 : lintcode上有啊
S*t
6 楼
做硬件的都涨了。。。
s*x
7 楼
Find the Connected Component in the Undirected Graph Find the number connected component in the undirected graph. Each node in the graph contains a label and a list of its neighbors. (a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.) Example Given graph: A------B C | | | | | | | | D E Return {A,B,D}, {C,E}. Since there are two connected component which is {A,B ,D}, {C,E} Find the Weak Connected Component in the Directed Graph Find the number Weak Connected Component in the directed graph. Each node in the graph contains a label and a list of its neighbors. (a connected set of a directed graph is a subgraph in which any two vertices are connected by direct edge path.) Example Given graph: A----->B C | | | | | | v v ->D E Return {A,B,D}, {C,E,F}. Since there are two connected component which are { A,B,D} and {C,E,F} Note Sort the element in the set in increasing order
【在 f**********n 的大作中提到】 : 老中面试官,问了个这个题目: : Find all connected components in an undirected graph. : 我尝试了DFS和BFS,不知道对不对,最后挂了。 : 大家有啥好解法?
g*7
8 楼
I have 30, 1/4 of my call holdings. MU will make it!
【在 h********r 的大作中提到】 : I have only 4 calls @0.25 and just support you. I hope I can got some from : mu to buy some Hallowen stuff for my kids. If it is not double, I will let : it rot away.
【在 s********x 的大作中提到】 : Find the Connected Component in the Undirected Graph : Find the number connected component in the undirected graph. Each node in : the graph contains a label and a list of its neighbors. (a connected : component (or just component) of an undirected graph is a subgraph in which : any two vertices are connected to each other by paths, and which is : connected to no additional vertices in the supergraph.) : Example : Given graph: : A------B C : | |
不对吧。你是在IDE里面跑的? 一开始cluster是 [-1,-1], 两个find后是[0,1] union后是[1,1] Anyways, the purpose of union is to set the corresponding index in cluster to the same Number
Union-Find is O(alpha(E)*E). the process is foreach edge in edges: union(edge.source, edge.target) //undirected... you can name whatever.. The complexity of union is not O(1) but O(alpha) which grows very slowly. Comparing with DFS/BFS it might actually have performance advantage because of compact implementation (implies smaller "constant" multiplier).