aboutsummaryrefslogtreecommitdiff
path: root/other/count_unreach_node.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/count_unreach_node.cpp')
-rw-r--r--other/count_unreach_node.cpp48
1 files changed, 48 insertions, 0 deletions
diff --git a/other/count_unreach_node.cpp b/other/count_unreach_node.cpp
new file mode 100644
index 0000000..bf7413b
--- /dev/null
+++ b/other/count_unreach_node.cpp
@@ -0,0 +1,48 @@
+// 2316. Count Unreachable Pairs of Nodes in an Undirected Graph
+#include "leetcode.h"
+
+/*
+ * given integer 'n', there is undirected graph with 'n' nodes, numbered 0 to 'n
+ * - 1' given 2d integer array 'edges' where 'edges[i] = [ai bi]' denotes that
+ * there exists an undirected edge connecting nodes ai and bi. return number of
+ * pairs of different nodes that are unreachable from each other
+ */
+
+class Solution {
+public:
+ long long countPairs(int n, vvd & edges) {
+ unordered_map<int, vector<int>> m;
+ for (int i = 0; i < edges.size(); i++) {
+ m[edges[i][0]].push_back(edges[i][0]);
+ m[edges[i][1]].push_back(edges[i][1]);
+ }
+ long long ans = ((long long)n * (n - 1)) / 2;
+ vector<int> vis(n, 0);
+ for (int i = 0; i < n; i++) {
+ if (vis[i] == 0) {
+ long long cnt = 0;
+ dfs(i, m, cnt, vis);
+ ans -= (cnt * (cnt - 1)) / 2;
+ }
+ }
+ return ans;
+ }
+
+private:
+ void dfs(int n, unordered_map<int, vector<int>> m, long long cnt,
+ vector<int> vis) {
+ vis[n] = 1;
+ cnt++;
+ for (auto i : m[n])
+ if (vis[i] == 0)
+ dfs(i, m, cnt, vis);
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd e1 = {{0, 1}, {0, 2}, {1, 2}};
+ vvd e2 = {{0, 2}, {0, 5}, {2, 4}};
+ printf("%lld\n", obj.countPairs(3, e1)); // expect: 0
+ printf("%lld\n", obj.countPairs(7, e2)); // expect: 14
+}