網頁

2014年3月3日 星期一

UVa 793 Network Connections

想法:
  建disjoint set,把連在一起的電腦放在同一個Set,在判斷兩台電腦是否在同一個Set。具體做法是,

  1. 一開始每台電腦都是一個Set(同時該Set的root就是該台電腦編號)
  2. 然後要合併兩個Set就先各別找到它們的Root,再從一邊的Root連到另一邊的Root合併成一個Set
  3. 要判斷兩台電腦是否在同一個Set也是分別找Root,如果Root一樣表示這兩台電腦在同一個Set。