Alice 和 Bob 共有一个无向图,其中包含 n 个节点和 3 种类型的边:
- 类型 1:只能由 Alice 遍历。
- 类型 2:只能由 Bob 遍历。
- 类型 3:Alice 和 Bob 都可以遍历。
给你一个数组
edges
,其中\(edges[i] = [type_i, u_i, v_i]\) 表示节点\(u_i\)和 \( v_i\) 之间存在类型为 \(type_i\) 的双向边。请你在保证图仍能够被 Alice 和 Bob 完全遍历的前提下,找出可以删除的最大边数。如果从任何节点开始,Alice 和 Bob 都可以到达所有其他节点,则认为图是可以完全遍历的。返回可以删除的最大边数,如果 Alice 和 Bob 无法完全遍历图,则返回 -1 。
力扣数据中心有
n
台服务器,分别按从0
到n-1
的方式进行了编号。它们之间以「服务器到服务器」点对点的形式相互连接组成了一个内部集群,其中连接connections
是无向的。从形式上讲,connections[i] = [a, b]
表示服务器a
和b
之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。「关键连接」 是在该集群中的重要连接,也就是说,假如我们将它移除,便会导致某些服务器无法访问其他服务器。
请你以任意顺序返回该集群内的所有 「关键连接」。
A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.
Given a tree of
n
nodes labelled from0
ton - 1
, and an array ofn - 1
edges
whereedges[i] = [ai, bi]
indicates that there is an undirected edge between the two nodesai
andbi
in the tree, you can choose any node of the tree as the root. When you select a nodex
as the root, the result tree has heighth
. Among all possible rooted trees, those with minimum height (i.e.min(h)
) are called minimum height trees (MHTs).Return a list of all MHTs’ root labels. You can return the answer in any order.
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
You are given an integer
n
denoting the number of nodes of a weighted directed graph. The nodes are numbered from0
ton - 1
.You are also given a 2D integer array
edges
where \(edges[i] = [from_i, to_i, weight_i]\) denotes that there exists a directed edge from \(from_i\) to \(to_i\) with weight \(weight_i\).Lastly, you are given three distinct integers
src1
,src2
, anddest
denoting three distinct nodes of the graph.Return the minimum weight of a subgraph of the graph such that it is possible to reach
dest
from bothsrc1
andsrc2
via a set of edges of this subgraph. In case such a subgraph does not exist, return-1
.A subgraph is a graph whose vertices and edges are subsets of the original graph. The weight of a subgraph is the sum of weights of its constituent edges.
You are given an array
pairs
, where \(pairs[i] = [x_i, y_i]\), and:- There are no duplicates.
- \(x_i < y_i\)
Let
ways
be the number of rooted trees that satisfy the following conditions:- The tree consists of nodes whose values appeared in
pairs
. - A pair \([x_i, y_i]\) exists in
pairs
if and only if \(x_i\) is an ancestor of \(y_i\) or \(y_i\) is an ancestor of \(x_i\). - Note: the tree does not have to be a binary tree.
Two ways are considered to be different if there is at least one node that has different parents in both ways.
Return:
0
ifways == 0
1
ifways == 1
2
ifways > 1
A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.
An ancestor of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.
两位玩家分别扮演猫和老鼠,在一张 无向 图上进行游戏,两人轮流行动。
图的形式是:
graph[a]
是一个列表,由满足ab
是图中的一条边的所有节点b
组成。老鼠从节点
1
开始,第一个出发;猫从节点2
开始,第二个出发。在节点0
处有一个洞。在每个玩家的行动中,他们 必须 沿着图中与所在当前位置连通的一条边移动。例如,如果老鼠在节点
1
,那么它必须移动到graph[1]
中的任一节点。此外,猫无法移动到洞中(节点
0
)。然后,游戏在出现以下三种情形之一时结束:
- 如果猫和老鼠出现在同一个节点,猫获胜。
- 如果老鼠到达洞中,老鼠获胜。
- 如果某一位置重复出现(即,玩家的位置和移动顺序都与上一次行动相同),游戏平局。
给你一张图
graph
,并假设两位玩家都都以最佳状态参与游戏:- 如果老鼠获胜,则返回
1
; - 如果猫获胜,则返回
2
; - 如果平局,则返回
0
。