| # | Title | Difficulty | Tag | Time, ms | Time, %

|------|----------------|-------------|-------------|----------|---------

| 2316 |[Count Unreachable Pairs of Nodes in an Undirected Graph](src/main/java/g2301_2400/s2316_count_unreachable_pairs_of_nodes_in_an_undirected_graph/Solution.java)| Medium || 32 | 100.00

| 2315 |[Count Asterisks](src/main/java/g2301_2400/s2315_count_asterisks/Solution.java)| Easy || 1 | 100.00

| 2312 |[Selling Pieces of Wood](src/main/java/g2301_2400/s2312_selling_pieces_of_wood/Solution.java)| Hard | Backtracking | 78 | 63.64

| 2311 |[Longest Binary Subsequence Less Than or Equal to K](src/main/java/g2301_2400/s2311_longest_binary_subsequence_less_than_or_equal_to_k/Solution.java)| Medium | String, Dynamic_Programming, Greedy, Memoization | 1 | 100.00

packageg2301_2400.s2316_count_unreachable_pairs_of_nodes_in_an_undirected_graph;

importjava.util.HashMap;

publicclassSolution {

publiclongcountPairs(intn,int[][]edges) {

DSUd =newDSU(n);

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

for (int[]e :edges) {

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

}

longans =0;

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

intp =d.findParent(i);

intcnt =map.containsKey(p) ?map.get(p) :0;

ans +=i -cnt;

map.put(p,map.getOrDefault(p,0) +1);

}

returnans;

}

privatestaticclassDSU {

int[]rank;

int[]parent;

DSU(intn) {

rank =newint[n +1];

parent =newint[n +1];

for (inti =1;i <=n;i++) {

parent[i] =i;

}

}

intfindParent(intnode) {

if (parent[node] ==node) {

returnnode;

}

parent[node] =findParent(parent[node]);

returnfindParent(parent[node]);

}

booleanunion(intx,inty) {

intpx =findParent(x);

intpy =findParent(y);

if (px ==py) {

returnfalse;

}

if (rank[px] >rank[py]) {

parent[py] =px;

}else {

parent[px] =py;

rank[py]++;

}

returntrue;

}

}

}

2316\. Count Unreachable Pairs of Nodes in an Undirected Graph

Medium

You are given an integer`n`. There is an**undirected** graph with`n` nodes, numbered from`0` to`n - 1`. You are given a 2D integer array`edges` where <code>edges[i] =[a_i, b_i]</code> denotes that there exists an**undirected** edge connecting nodes <code>a_i</code> and <code>b_i</code>.

Return_the**number of pairs** of different nodes that are**unreachable** from each other_.

**Example 1:**

**Input:** n = 3, edges =[[0,1],[0,2],[1,2]]

**Output:** 0

**Explanation:** There are no pairs of nodes that are unreachable from each other.

Therefore, we return 0.

**Example 2:**

**Input:** n = 7, edges =[[0,2],[0,5],[2,4],[1,6],[5,4]]

**Output:** 14

**Explanation:** There are 14 pairs of nodes that are unreachable from each other:[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]].

Therefore, we return 14.

**Constraints:**

* <code>1 <= n <= 10⁵</code>

* <code>0 <= edges.length <= 2 * 10⁵</code>

* <code>0 <= a_i, b_i < n</code>

* <code>a_i != b_i</code>

* There are no repeated edges.

newThread(() ->foo.first(() ->fooData[0]++)).start();

newThread(() ->foo.second(() ->fooData[0]++)).start();

newThread(() ->foo.third(() ->fooData[0]++)).start();

TimeUnit.MILLISECONDS.sleep(500);

TimeUnit.MILLISECONDS.sleep(600);

assertThat(fooData[0],equalTo(3));

}

}

packageg2301_2400.s2316_count_unreachable_pairs_of_nodes_in_an_undirected_graph;

importstaticorg.hamcrest.CoreMatchers.equalTo;

importstaticorg.hamcrest.MatcherAssert.assertThat;

importorg.junit.jupiter.api.Test;

classSolutionTest {

voidcountPairs() {

assertThat(newSolution().countPairs(3,newint[][] {{0,1}, {0,2}, {1,2}}),equalTo(0L));

}

voidcountPairs2() {

assertThat(

newSolution().countPairs(7,newint[][] {{0,2}, {0,5}, {2,4}, {1,6}, {5,4}}),

equalTo(14L));

}

}