package com.dataStructure.graph;
// 求無權圖的聯通分量
public class Components {
	private Graph graph;
	// 存放輸入的數組
	private Boolean[] visited;
	// 存放節點被訪問狀態
	private int componentCount;
	// 連通分量的數量
	private int[] mark;
	// 存儲節點所屬聯通分量的標記
	// 構造函數，初始化私有屬性
	public Components(Graph graph) {
		this.graph = graph;
		componentCount = 0;
		// 連通分量初始數量為 0
		visited = new Boolean[graph.V()];
		mark = new int[graph.V()];
		for (int i = 0; i < graph.V(); i++) {
			visited[i] = false;
			// 節點初始訪問狀態為 false
			mark[i] = -1;
			// 節點初始連通分量標記為 -1
		}
		for (int i = 0; i < graph.V(); i++) {
			// 對于未被訪問的節點進行 dfs深度優先遍歷
			if (!visited[i]) {
				dfs(i);
				componentCount++;
				// 對一個節點進行dfs 到底后，一個連通分量結束，數量+1
			}
		}
	}
	private void dfs(int i) {
		visited[i] = true;
		// 節點 i 已被訪問
		mark[i] = componentCount;
		// 節點 i 屬于當前連通分量的數量（標記）
		for (int node : graph.adjacentNode(i)) {
			// 遍歷圖中節點 i 的鄰接節點
			if (!visited[node]) // 對未被訪問的鄰接節點進行 dfs
			dfs(node);
		}
	}
	public Boolean isConnected(int v, int w) {
		return mark[v] == mark[w];
		// 根據兩節點所屬連通分量的標記判斷兩節點是否相連
	}
	public int getComponentCount() {
		return componentCount;
		// 返回 graph 中連通分量的數量
	}
}
//public class Components {
//
//  private Graph G;          // 圖的引用
//  private boolean[] visited; // 記錄dfs的過程中節點是否被訪問
//  private int ccount;     // 記錄聯通分量個數
//  private int[] id;      // 每個節點所對應的聯通分量標記
//
//  // 圖的深度優先遍歷
//  private void dfs(int v) {
//
//    visited[v] = true; // 節點 v 的訪問狀態置為 true
//    id[v] = ccount; // 節點 v 對應的聯通標記設置為 ccount
//
//    // 遍歷節點 v 的鄰接點 i
//    for (int i : G.adjacentNode(v)) {
//      // 如果鄰接點 i 尚未被訪問
//      if (!visited[i])
//        // 對鄰接點 i 進行深度優先遍歷
//        dfs(i);
//    }
//  }
//
//  // 構造函數, 求出無權圖的聯通分量
//  public Components(Graph graph) {
//
//    // 算法初始化
//    G = graph;
//
//    // visited 數組存儲 圖G 中 節點的被訪問狀態
//    visited = new boolean[G.V()];
//
//    // id 數組存儲 圖G 中 節點所屬連通分量的標記
//    id = new int[G.V()];
//
//    // 連通分量數量初始化為 0
//    ccount = 0;
//
//    // 將 visited 數組全部置為 false； id 數組全部置為 -1
//    for (int i = 0; i < G.V(); i++) {
//      visited[i] = false;
//      id[i] = -1;
//    }
//
//    // 求圖的聯通分量
//    for (int i = 0; i < G.V(); i++)
//      // 訪問一個未曾被訪問的節點
//      if (!visited[i]) {
//        // 對其進行深度優先遍歷
//        dfs(i);
//        ccount++;
//      }
//  }
//
//  // 返回圖的聯通分量個數
//  int count() {
//    return ccount;
//  }
//
//  // 查詢點v和點w是否聯通（節點v 和 w 的聯通分量的標記是否相同
//  boolean isConnected(int v, int w) {
//    assert v >= 0 && v < G.V();
//    assert w >= 0 && w < G.V();
//    return id[v] == id[w];
//  }
//}