aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--find_champion_2.c40
-rw-r--r--find_champion_2.py29
2 files changed, 69 insertions, 0 deletions
diff --git a/find_champion_2.c b/find_champion_2.c
new file mode 100644
index 0000000..a6282bb
--- /dev/null
+++ b/find_champion_2.c
@@ -0,0 +1,40 @@
+// 2924. Find Champion II
+#include "leetcode.h"
+
+/*
+ * there are 'n' teams numbered from 0 to 'n - 1' in a tournament; each team is
+ * also a node in DAG. you are given the integer 'n' and a 0-indexed 2d integer
+ * array 'edges' of length 'm' representing the DAG, where 'edges[i] = [u_i,
+ * v_i]' indicates that is a directed edge from team 'u_i' to team 'v_i' in the
+ * graph. a directed edge from 'a' to 'b' in the graph means that team 'a' is
+ * strong than team 'b' and team 'b' is weaker than team 'a'. return the team
+ * that will be the champion of the tournament if there is a unique champion,
+ * otherwise return -1.
+ */
+
+int findChampion(int n, int **edges, int edgesSize, int *edgesColSize) {
+ char state[n];
+ memset(state, 'w', sizeof(state));
+ for (int i = 0; i < edgesSize; i++)
+ state[edges[i][1]] = 'l';
+ int cnt = 0, ans = 0;
+ for (int i = 0; i < n; i++)
+ if (state[i] == 'w') {
+ cnt++;
+ ans = i;
+ }
+ return cnt == 1 ? ans : -1;
+}
+
+int main() {
+ int e1i[2][2] = {{0, 1}, {1, 2}}, e2i[3][2] = {{0, 2}, {1, 3}, {1, 2}};
+ struct two_d_arr e1, e2;
+ two_d_arr_init(&e1, 2, 2, e1i);
+ two_d_arr_init(&e2, 3, 2, e2i);
+ printf("%d\n", findChampion(3, e1.arr, e1.row_size, e1.col_size)); // expect:
+ // 0
+ printf("%d\n",
+ findChampion(4, e2.arr, e2.row_size, e2.col_size)); // expect: -1
+ two_d_arr_free(&e1);
+ two_d_arr_free(&e2);
+}
diff --git a/find_champion_2.py b/find_champion_2.py
new file mode 100644
index 0000000..ac139fe
--- /dev/null
+++ b/find_champion_2.py
@@ -0,0 +1,29 @@
+# 2924. Find Champion II
+
+"""
+there are 'n' teams numbered from 0 to 'n - 1' in a tournament; each team is
+also a node in DAG. you are given the integer 'n' and a 0-indexed 2d integer
+array 'edges' of length 'm' representing the DAG, where 'edges[i] = [u_i,
+v_i]' indicates that is a directed edge from team 'u_i' to team 'v_i' in the
+graph. a directed edge from 'a' to 'b' in the graph means that team 'a' is
+strong than team 'b' and team 'b' is weaker than team 'a'. return the team
+that will be the champion of the tournament if there is a unique champion,
+otherwise return -1.
+"""
+
+
+class Solution(object):
+ def findChampion(self, n, edges):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :rtype: int
+ """
+ weak = {b for a, b in edges}
+ return -1 if len(weak) < n - 1 else n * (n - 1) // 2 - sum(weak)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findChampion(n=3, edges=[[0, 1], [1, 2]]))
+ print(obj.findChampion(n=4, edges=[[0, 2], [1, 3], [1, 2]]))