\chapter{Graph}

\section{Alien Dictionary} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

\textbf{Example:}

Given the following words in dictionary,

\begin{Code}

[

"wrt",

"wrf",

"er",

"ett",

"rftt"

]

\end{Code}

The correct order is: \code{"wertf"}.

\textbf{Note:}

1. You may assume all letters are in lowercase.

2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.

3. If the order is invalid, return an empty string.

4. There may be multiple valid order of letters, return any one of them is fine.

\subsubsection{Solution}

\begin{Code}

public String alienOrder(String[] words) {

int[] indegree = new int[26];

Arrays.fill(indegree, -1);

int count = 0;

for (String word : words) {

for (char c : word.toCharArray()) {

if (indegree[c - 'a'] != 0) {

indegree[c - 'a'] = 0;

count++;

}

}

}

HashMap<Character, Set<Character>> map = new HashMap<>();

for (int i = 0; i < words.length - 1; i++) {

String first = words[i], second = words[i + 1];

int len = Math.min(first.length(), second.length());

for (int j = 0; j < len; j++) {

if (first.charAt(j) != second.charAt(j)) {

Set<Character> set = map.get(first.charAt(j));

if (set == null) {

set = new HashSet<Character>();

map.put(first.charAt(j), set);

}

if (set.add(second.charAt(j))) {

indegree[second.charAt(j) - 'a']++;

}

break;

} else {

if (j + 1 >= second.length() && j + 1 < first.length()) { return ""; }

}

}

}

Queue<Character> queue = new LinkedList<Character>();

for (int i = 0; i < indegree.length; i++) {

if (indegree[i] == 0) {

queue.add((char) ('a' + i));

}

}

StringBuilder sb = new StringBuilder();

while (!queue.isEmpty()) {

Character from = queue.poll();

sb.append(from);

Set<Character> set = map.get(from);

if (set != null) {

for (Character to : map.get(from)) {

if (--indegree[to - 'a'] == 0) {

queue.add(to);

}

}

}

}

return sb.length() != count ? "" : sb.toString();

}

\end{Code}

\section{Course Schedule} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: \code{[0,1]}

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

\code{2, [[1,0]]}

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

\code{2, [[1,0],[0,1]]}

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

\textbf{Note:}

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

2. You may assume that there are no duplicate edges in the input prerequisites.

\textbf{Hints:}

1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.

3. Topological sort could also be done via BFS.

\subsubsection{Solution}

\begin{Code}

/**

* 这题就是典型的拓扑排序

*/

public boolean canFinish(int numCourses, int[][] prerequisites) {

int[] indegree = new int[numCourses];

HashMap<Integer, Set<Integer>> map = new HashMap<>();

for (int[] f : prerequisites) {

int from = f[1], to = f[0];

Set<Integer> set = map.get(from);

if (set == null) {

set = new HashSet<>();

map.put(from, set);

}

/**

* 这里要防止同一条边计了多次

*/

if (set.add(to)) {

indegree[to]++;

}

}

Queue<Integer> queue = new LinkedList<>();

List<Integer> list = new LinkedList<>();

for (int i = 0; i < indegree.length; i++) {

if (indegree[i] == 0) {

queue.add(i);

}

}

while (!queue.isEmpty()) {

Integer n = queue.poll();

list.add(n);

Set<Integer> set = map.get(n);

if (set != null) {

for (Integer k : set) {

if (--indegree[k] == 0) {

queue.add(k);

}

}

}

}

return list.size() == numCourses;

}

\end{Code}

\section{Course Schedule II} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

\code{2, [[1,0]]}

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is \code{[0,1]}

\code{4, [[1,0],[2,0],[3,1],[3,2]]}

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is \code{[0,1,2,3]}. Another correct ordering is \code{[0,2,1,3]}.

\textbf{Note:}

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

2. You may assume that there are no duplicate edges in the input prerequisites.

\textbf{Hints:}

1. This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.

3. Topological sort could also be done via BFS.

\subsubsection{Solution}

\begin{Code}

public int[] findOrder(int numCourses, int[][] prerequisites) {

int[] indegree = new int[numCourses];

HashMap<Integer, Set<Integer>> map = new HashMap<>();

for (int[] pre : prerequisites) {

int from = pre[1], to = pre[0];

Set<Integer> set = map.get(from);

if (set == null) {

set = new HashSet<Integer>();

map.put(from, set);

}

/**

* 这里要避免添加多次

*/

if (set.add(to)) {

indegree[to]++;

}

}

Queue<Integer> queue = new LinkedList<>();

for (int i = 0; i < numCourses; i++) {

if (indegree[i] == 0) {

queue.add(i);

}

}

int count = 0;

int[] result = new int[numCourses];

while (!queue.isEmpty()) {

Integer n = queue.poll();

result[count++] = n;

Set<Integer> set = map.get(n);

if (set != null) {

for (Integer k : set) {

if (--indegree[k] == 0) {

queue.add(k);

}

}

}

}

return count == numCourses ? result : new int[0];

}

\end{Code}

\section{Longest Increasing Path in a Matrix} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

\textbf{Example 1:}

\begin{Code}

nums = [

[9,9,4],

[6,6,8],

[2,1,1]

]

\end{Code}

Return 4

The longest increasing path is [1, 2, 6, 9].

\textbf{Example 2:}

\begin{Code}

nums = [

[3,4,5],

[3,2,6],

[2,2,1]

]

\end{Code}

Return 4

The longest increasing path is \code{[3, 4, 5, 6]}. Moving diagonally is not allowed.

\subsubsection{Solution}

\begin{Code}

public int longestIncreasingPath(int[][] matrix) {

if (matrix.length == 0) {

return 0;

}

int row = matrix.length, col = matrix[0].length;

int max = 0;

int[][] cache = new int[row][col];

for (int i = 0; i < row; i++) {

for (int j = 0; j < col; j++) {

int len = dfs(matrix, i, j, cache);

max = Math.max(max, len);

}

}

return max;

}

private int dfs(int[][] matrix, int i, int j, int[][] cache) {

if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {

return 0;

}

if (cache[i][j] > 0) {

return cache[i][j];

}

int max = 1;

int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};

for (int k = 0; k < dx.length; k++) {

int x = i + dx[k], y = j + dy[k];

if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length

|| matrix[x][y] <= matrix[i][j]) {

continue;

}

max = Math.max(max, dfs(matrix, x, y, cache) + 1);

}

cache[i][j] = max;

return max;

}

\end{Code}

\section{Sequence Reconstruction} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

\textbf{Example 1:}

\textbf{Input:}

org: [1,2,3], seqs: [[1,2],[1,3]]

\textbf{Output:}

false

\textbf{Explanation:}

[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.

Example 2:

\textbf{Input:}

org: [1,2,3], seqs: [[1,2]]

\textbf{Output:}

false

\textbf{Explanation:}

The reconstructed sequence can only be [1,2].

\textbf{Example 3:}

\textbf{Input:}

org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]

\textbf{Output:}

true

\textbf{Explanation:}

The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

\textbf{Example 4:}

\textbf{Input:}

org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]

\textbf{Output:}

true

\subsubsection{Solution}

\begin{Code}

\end{Code}

\section{Number of Islands} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given a 2d grid map of \code{'1'}s (land) and \code{'0'}s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

\textbf{Example 1:}

\begin{Code}

11110

11010

11000

00000

\end{Code}

Answer: 1

\textbf{Example 2:}

\begin{Code}

11000

11000

00100

00011

\end{Code}

Answer: 3

\subsubsection{Solution I}

\begin{Code}

public int numIslands(char[][] grid) {

int num = 0;

for (int i = 0; i < grid.length; i++) {

for (int j = 0; j < grid[0].length; j++) {

if (grid[i][j] == '1') {

num++;

dfs(grid, i, j);

}

}

}

return num;

}

private void dfs(char[][] grid, int i, int j) {

if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {

return;

}

grid[i][j] = '0';

dfs(grid, i - 1, j);

dfs(grid, i + 1, j);

dfs(grid, i, j - 1);

dfs(grid, i, j + 1);

}

\end{Code}

\subsubsection{Solution II}

\begin{Code}

public int numIslands(char[][] grid) {

int num = 0;

for (int i = 0; i < grid.length; i++) {

for (int j = 0; j < grid[0].length; j++) {

if (grid[i][j] == '1') {

num++;

bfs(grid, i, j);

}

}

}

return num;

}

private void bfs(char[][] grid, int i, int j) {

Queue<int[]> queue = new LinkedList<int[]>();

queue.add(new int[] {i, j});

int[] dx = {-1, 1, 0, 0}, dy = {0, 0, - 1, 1};

while (!queue.isEmpty()) {

int[] pos = queue.poll();

int x = pos[0], y = pos[1];

for (int k = 0; k < dx.length; k++) {

int x0 = x + dx[k], y0 = y + dy[k];

if (x0 >= 0 && x0 < grid.length && y0 >= 0 && y0 < grid[0].length && grid[x0][y0] == '1') {

grid[x0][y0] = '0';

queue.add(new int[] {x0, y0});

}

}

}

}

\end{Code}

\section{Number of Islands II} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

\textbf{Example:}

Given m = 3, n = 3, positions = \code{[[0,0], [0,1], [1,2], [2,1]]}.

Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

\begin{Code}

0 0 0

0 0 0

0 0 0

\end{Code}

Operation 1: addLand(0, 0) turns the water at grid[0][0] into a land.

\begin{Code}

1 0 0

0 0 0 Number of islands = 1

0 0 0

\end{Code}

Operation 2: addLand(0, 1) turns the water at grid[0][1] into a land.

\begin{Code}

1 1 0

0 0 0 Number of islands = 1

0 0 0

\end{Code}

Operation 3: addLand(1, 2) turns the water at grid[1][2] into a land.

\begin{Code}

1 1 0

0 0 1 Number of islands = 2

0 0 0

\end{Code}

Operation 4: addLand(2, 1) turns the water at grid[2][1] into a land.

\begin{Code}

1 1 0

0 0 1 Number of islands = 3

0 1 0

\end{Code}

We return the result as an array: \code{[1, 1, 2, 3]}

\textbf{Challenge:}

Can you do it in time complexity O(k log mn), where k is the length of the positions?

\subsubsection{Solution}

\begin{Code}

private int[] mRoots;

private int mCount;

// 时间复杂度klgmn

public List<Integer> numIslands2(int m, int n, int[][] positions) {

List<Integer> list = new LinkedList<Integer>();

mRoots = new int[m * n];

/**

* 首先都指向-1，稍后添加岛时再初始化

*/

Arrays.fill(mRoots, -1);

for (int[] p : positions) {

int x = p[0], y = p[1], z = x * n + y;

/**

* 指向自己

*/

mRoots[z] = z;

mCount++;

int[] dx = {-1, 1, 0, 0}, dy = {0, 0, 1, -1};

for (int i = 0; i < dx.length; i++) {

int x0 = x + dx[i], y0 = y + dy[i], z0 = x0 * n + y0;

if (x0 < 0 || x0 >= m || y0 < 0 || y0 >= n || mRoots[z0] == -1) {

continue;

}

/**

* 这里是给z合并到z0中去，即新添加的这个岛要合到老的岛上去

*/

union(z, z0);

}

list.add(mCount);

}

return list;

}

private void union(int x, int y) {

int x0 = findIsLand(x);

int y0 = findIsLand(y);

if (x0 != y0) {

mRoots[x0] = y0;

mCount--;

}

}

private int findIsLand(int root) {

while (root != mRoots[root]) {

root = mRoots[root];

}

return root;

}

\end{Code}

\section{Longest Consecutive Sequence} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,

Given \code{[100, 4, 200, 1, 3, 2]},

The longest consecutive elements sequence is \code{[1, 2, 3, 4]}. Return its length: 4.

Your algorithm should run in O(n) complexity.

\subsubsection{Solution}

\begin{Code}

/**

* map中保存的是某个点所在的联通块长度，不过要注意的这个连通块两端的点才是准的，中间的点可能不准

* 所以我们每次新插入一个点时，一定要更新连通块两端的点

*/

public int longestConsecutive(int[] nums) {

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

int res = 0;

for (int i = 0; i < nums.length; i++) {

int n = nums[i];

if (!map.containsKey(n)) {

int left = map.containsKey(n - 1) ? map.get(n - 1) : 0;

int right = map.containsKey(n + 1) ? map.get(n + 1) : 0;

int len = left + right + 1;

// 这句一定不能掉，因为map会查重的，如果这里n没丢到map里，后面再出现重复的n会被覆盖

map.put(n, len);

res = Math.max(res, len);

map.put(n - left, len);

map.put(n + right, len);

}

}

return res;

}

\end{Code}

\section{Surrounded Regions} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.

2. 0 - A gate.

3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

\begin{Code}

INF -1 0 INF

INF INF INF -1

INF -1 INF -1

0 -1 INF INF

\end{Code}

After running your function, the 2D grid should be:

\begin{Code}

3 -1 0 1

2 2 1 -1

1 -1 2 -1

0 -1 3 4

\end{Code}

\subsubsection{Solution I}

\begin{Code}

/**

* Union Find法

*/

private int[] mRoot; // union find set

private boolean[] mHasEdge; // whether an union has an 'O' which is on the edge of the matrix

public void solve(char[][] board) {

if (board.length == 0) {

return;

}

// init, every char itself is an union

int row = board.length, col = board[0].length;

mRoot = new int[row * col];

mHasEdge = new boolean[mRoot.length];

for (int i = 0; i < mRoot.length; i++) {

mRoot[i] = i;

}

for (int i = 0; i < mHasEdge.length; i++) {

int x = i / col, y = i % col;

mHasEdge[i] = (board[x][y] == 'O' && (x == 0 || x == row - 1 || y == 0 || y == col - 1));

}

// iterate the matrix, for each char, union it + its upper char + its right char if they equals to each other

for (int i = 0; i < mRoot.length; i++) {

int x = i / col, y = i % col, up = x - 1, right = y + 1;

if (up >= 0 && board[x][y] == board[up][y]) union(i, i - col);

if (right < col && board[x][y] == board[x][right]) union(i, i + 1);

}

// for each char in the matrix, if it is an 'O' and its union doesn't has an 'edge O', the whole union should be setted as 'X'

for (int i = 0; i < mRoot.length; i++) {

int x = i / col, y = i % col;

if (board[x][y] == 'O' && !mHasEdge[find(i)])

board[x][y] = 'X';

}

}

private void union(int x, int y) {

int rootX = find(x);

int rootY = find(y);

// if there is an union has an 'edge O',the union after merge should be marked too

mRoot[rootX] = rootY;

mHasEdge[rootY] = mHasEdge[rootX] || mHasEdge[rootY];

}

private int find(int root) {

if (mRoot[root] == root) {

return root;

}

// 在找的过程中直接联通到根节点了，这样的好处是加速未来的查找

mRoot[root] = find(mRoot[root]);

return mRoot[root];

}

\end{Code}

\subsubsection{Solution II}

\begin{Code}

/**

* BFS法

* 给与边界的O相邻的所有O点都标为+，然后剩下的O肯定是不与边界O相邻的，则必然是被X包围的，

* 将这些O标为X后，再给剩下的+都还原为O即可

*/

public void solve2(char[][] board) {

if (board.length == 0) {

return;

}

int row = board.length, col = board[0].length;

Queue<int[]> queue = new LinkedList<int[]>();

for (int i = 0; i < col; i++) {

enqueue(board, 0, i, queue);

enqueue(board, row - 1, i, queue);

}

for (int i = 0; i < row; i++) {

enqueue(board, i, 0, queue);

enqueue(board, i, col - 1, queue);

}

while (!queue.isEmpty()) {

int[] pos = queue.poll();

int x = pos[0], y = pos[1];

enqueue(board, x - 1, y, queue);

enqueue(board, x + 1, y, queue);

enqueue(board, x, y + 1, queue);

enqueue(board, x, y - 1, queue);

}

for (int i = 0; i < row; i++) {

for (int j = 0; j < col; j++) {

if (board[i][j] == 'O') {

board[i][j] = 'X';

} else if (board[i][j] == '+') {

board[i][j] = 'O';

}

}

}

}

private void enqueue(char[][] board, int i, int j, Queue<int[]> queue) {

if (i >= 0 && i < board.length && j >= 0 && j < board[0].length && board[i][j] == 'O') {

board[i][j] = '+';

queue.add(new int[]{i, j});

}

}

\end{Code}

\subsubsection{Solution III}

\begin{Code}

/**

* DFS法

* 数据量大时可能Stack Overflow

*/

public void solve3(char[][] board) {

if (board.length == 0) {

return;

}

int row = board.length, col = board[0].length;

for (int i = 0; i < col; i++) {

dfs(board, 0, i);

dfs(board, row - 1, i);

}

for (int i = 0; i < row; i++) {

dfs(board, i, 0);

dfs(board, i, col - 1);

}

for (int i = 0; i < row; i++) {

for (int j = 0; j < col; j++) {

if (board[i][j] == 'O') {

board[i][j] = 'X';

} else if (board[i][j] == '+') {

board[i][j] = 'O';

}

}

}

}

private void dfs(char[][] board, int i, int j) {

if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') {

return;

}

board[i][j] = '+';

dfs(board, i - 1, j);

dfs(board, i + 1, j);

dfs(board, i, j + 1);

dfs(board, i, j - 1);

}

\end{Code}

\section{Graph Valid Tree} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

\textbf{Note:} you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

\subsubsection{Solution I}

\begin{Code}

// 耗时1ms

public boolean validTree(int n, int[][] edges) {

/**

* 每个点都有一个另一个点指向它，唯独root是没有的，所以边数比点数少了1

*/

if (edges.length != n - 1) {

return false;

}

int[] nums = new int[n];

/**

* 先初始化这n个点都指向自己

*/

for (int i = 0; i < n; i++) {

nums[i] = i;

}

// perform union find

for (int i = 0; i < edges.length; i++) {

int x = find(nums, edges[i][0]);

int y = find(nums, edges[i][1]);

/**

* 既然题目中已经说明不会有重复的边，所以如果x==y说明x和y已经有一条路径相通了，

* 如果再多一条路径就要构成环了，所以这里直接return false

*/

if (x == y) return false;

// union

nums[x] = y;

}

return true;

}

int find(int nums[], int i) {

for (; nums[i] != i; i = nums[i]);

return i;

}

\end{Code}

\subsubsection{Solution II}

\begin{Code}

/**

* 采用DFS方法

*/

// 耗时6ms

public boolean validTree2(int n, int[][] edges) {

List<Integer>[] graph = new ArrayList[n];

for (int i = 0; i < n; i++) {

graph[i] = new ArrayList<>();

}

for (int i = 0; i < edges.length; i++) {

graph[edges[i][0]].add(edges[i][1]);

graph[edges[i][1]].add(edges[i][0]);

}

boolean[] visited = new boolean[n];

/**

* 这里从任意一点开始DFS都可以

*/

if (!dfs(graph, visited, 0, -1)) {

return false;

}

for (int i = 0; i < n; i++) {

if (!visited[i]) {

return false;

}

}

return true;

}

/**

* 采用DFS从某个点开始遍历整个图，

* @start 当前节点

* @parent 为了避免逆向遍历，因为parent肯定是访问过的，所以为了避免看作重复访问，这里排除了一下

* @return 是否无环

*/

private boolean dfs(List<Integer>[] graph, boolean[] visited, int start, int parent) {

visited[start] = true;

for (int i = 0; i < graph[start].size(); i++) {

int to = graph[start].get(i);

if (to == parent) {

continue;

}

if (visited[to]) {

return false;

}

if (!dfs(graph, visited, to, start)) {

return false;

}

}

return true;

}

\end{Code}

\section{Number of Connected Components in an Undirected Graph} %%%%%%%%%%%%%%%%%%%%%%

\subsubsection{Description}