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 find the number of connected components in an undirected graph.

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.

* Method 1: Union-find O(lg*N)

```Java

class Solution {

private int[] uf;

public int countComponents(int n, int[][] edges) {

this.uf = new int[n];

for(int i = 0; i < n; i++) this.uf[i] = i;

for(int[] e : edges){

union(e[0], e[1]);

}

int res = 0;

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

if(uf[i] == i) res++;

}

return res;

}

private int find(int i){

if(uf[i] != i){

uf[i] = find(uf[i]);

}

return uf[i];

}

private void union(int i, int j){

int p = find(i);

int q = find(j);

uf[p] = q;

}

}

```

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

* Method: pq O(n^2)

```Java

class Solution {

public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {

PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){

@Override

public int compare(int[] a, int[] b){

return nums1[a[0]] + nums2[a[1]] - nums1[b[0]] - nums2[b[1]];

}

});

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

for(int j = 0; j < nums2.length; j++){

pq.offer(new int[]{i, j});

}

}

List<int[]> result = new ArrayList<>();

int count = 0;

while(!pq.isEmpty() && count < k){

++count;

int[] cur = pq.poll();

result.add(new int[]{nums1[cur[0]], nums2[cur[1]]});

}

return result;

}

}

```

* Method 2:


```Java

class Solution {

public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {

List<int[]> result = new ArrayList<>();

if(nums1.length == 0 || nums2.length == 0 || k == 0) return result;

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->{

return a[0] + a[1] - b[0] - b[1];

});

//[0]: number from first arr

//[1]: number from second arr

//[2]: index of number in second arr

for(int i = 0; i < nums1.length; i++) pq.offer(new int[]{nums1[i], nums2[0], 0});

while(k-- > 0 && !pq.isEmpty()){

int[] cur = pq.poll();

result.add(new int[]{cur[0], cur[1]});

if(cur[2] + 1 == nums2.length) continue;

pq.offer(new int[]{cur[0], nums2[cur[2] + 1], cur[2] + 1});

}

return result;

}

}

```

### Reference

1. [simple Java O(KlogK) solution with explanation](https://leetcode.com/problems/find-k-pairs-with-smallest-sums/discuss/84551/simple-Java-O(KlogK)-solution-with-explanation)

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.

Note that the inputs "root" and "target" are actually TreeNodes.

The descriptions of the inputs above are just serializations of these objects.

Note:

1. The given tree is non-empty.

2. Each node in the tree has unique values 0 <= node.val <= 500.

3. The target node is a node in the tree.

4. 0 <= K <= 1000.

* Method: Undirected graph, tree

```Java

/**

class Solution {

private Map<TreeNode, List<TreeNode>> graph;

public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {

this.graph = new HashMap<>();

dfs(root); // Construct a undirected graph

// Use bfs to find the result;

int level = 0;

Queue<TreeNode> q = new LinkedList<>();

q.offer(target);

Set<TreeNode> visited = new HashSet<>();

visited.add(target);

while(!q.isEmpty() && level < K){

int size = q.size();

for(int sz = 0; sz < size; sz++){

TreeNode cur = q.poll();

List<TreeNode> neighbours = graph.get(cur);

for(TreeNode node: neighbours){

if(visited.contains(node)) continue;

visited.add(node);

q.offer(node);

}

}

level++;

}

List<Integer> result = new ArrayList<>();

if(level == K){

while(!q.isEmpty()) result.add(q.poll().val);

}

return result;

}

private void dfs(TreeNode node){

List<TreeNode> neighbours = graph.getOrDefault(node, new ArrayList<>());

if(node.left != null){

neighbours.add(node.left);

List<TreeNode> lefts = graph.getOrDefault(node.left, new ArrayList<>());

lefts.add(node);

graph.put(node.left, lefts);

dfs(node.left);

}

if(node.right != null){

neighbours.add(node.right);

List<TreeNode> rights = graph.getOrDefault(node.right, new ArrayList<>());

rights.add(node);

graph.put(node.right, rights);

dfs(node.right);

}

graph.put(node, neighbours);

}

}

```

In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.

Two nodes of a binary tree are cousins if they have the same depth, but have different parents.

We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.

Return true if and only if the nodes corresponding to the values x and y are cousins.

Note:

* The number of nodes in the tree will be between 2 and 100.

* Each node has a unique integer value from 1 to 100.

* Method: Bfs

```Java

/**

class Solution {

public boolean isCousins(TreeNode root, int x, int y) {

if(root == null || root.val == x || root.val == y) return false;

Queue<TreeNode> q = new LinkedList<>();

Set<Integer> set = new HashSet<>();

set.add(root.val);

q.offer(root);

while(!q.isEmpty()){

int size = q.size();

for(int p = 0; p < size; p++){

TreeNode node = q.poll();

// check if left and right belongs to same parent

if(node.left != null && node.right != null){

if((node.left.val == x && node.right.val == y)

|| (node.left.val == y && node.right.val == x)) return false;

}

if(node.left != null){

q.offer(node.left);

set.add(node.left.val);

}

if(node.right != null){

q.offer(node.right);

set.add(node.right.val);

}

}

if((!set.contains(x) && set.contains(y)) || (set.contains(x) && !set.contains(y))) return false;

else if(set.contains(x) && set.contains(y)) return true;

}

return true;

}

}

```