[普林斯顿算法公开课]并查集解决渗透问题

Tue, 08 Nov 2016 13:39:00 +0800

Percolation.java

运用题目给出的API来解决问题.
第一个文件是Percolation.java, 用来编写解决单个渗透问题相关代码.
API:

public class Percolation {
   public Percolation(int n)                // create n-by-n grid, with all sites blocked
   public void open(int row, int col)       // open site (row, col) if it is not open already
   public boolean isOpen(int row, int col)  // is site (row, col) open?
   public boolean isFull(int row, int col)  // is site (row, col) full?
   public boolean percolates()              // does the system percolate?

   public static void main(String[] args)   // test client (optional)
}

大体思想是, 建立一个查是否渗透的并查集, 只要最上面一排和最下面一排属于一个集合就认为是渗透的. 但是判断每两个节点是否联通需要额外的$n^2$的时间, 显然不合适.
我们引入两个假节点分别为top节点和down节点, 再把top节点与最上一排的节点连接, down节点与最下一排的节点连接, 这样渗透问题就等价转换为上下两个节点是否联通.
之后,每次打开一个节点时,只需搜索它的上下左右是否打开,如果打开就把该节点加入打开的节点的集合即可.
需要注意的两点:

并查集 on 子恒的博客

[普林斯顿算法公开课]并查集解决渗透问题

Percolation.java