python3 解法, 执行用时: 964 ms, 内存消耗: 82.5 MB, 提交时间: 2023-10-26 23:50:31
class Solution:
def minimumCost(self, cost: List[int], roads: List[List[int]]) -> int:
n = len(cost)
G = [[] for i in range(n)]
for i,j in roads:
G[i].append(j)
G[j].append(i)
low = [n] * n
seen = {-1: -1}
cut = [0] * n
res = []
inf = float('inf')
def tarjan(i, pre):
seen[i] = len(seen) + 1
children = 0
min_cost = inf
count_cut = 0
for j in G[i]:
if j in seen:
low[i] = min(low[i], seen[j])
continue
children += 1
cur_cost, cur_cut = tarjan(j, i)
low[i] = min(low[i], low[j])
if seen[i] <= low[j]:
if i != root or children > 1:
cut[i] = 1
cost[i] = inf
if i == root or seen[i] > low[j]:
min_cost = min(min_cost, cur_cost)
count_cut += cur_cut
min_cost = min(min_cost, cost[i])
count_cut += cut[i] > 0
if count_cut + (i != root) < 2 and seen[pre] <= low[i] and cut[i] == 0:
res.append(min_cost)
return [min_cost, count_cut]
tarjan(root:= 0, -1)
return sum(res) - max(res)
python3 解法, 执行用时: 1076 ms, 内存消耗: 109.9 MB, 提交时间: 2023-10-26 23:50:08
class Solution:
def minimumCost(self, cost: List[int], roads: List[List[int]]) -> int:
n = len(cost)
G = [set() for i in range(n)]
for i,j in roads:
G[i].add(j)
G[j].add(i)
low = [n] * n
seen = {}
cut = [0] * n
def tarjan(i):
seen[i] = len(seen) + 1
children = 0
for j in G[i]:
if j in seen:
low[i] = min(low[i], seen[j])
continue
children += 1
tarjan(j)
low[i] = min(low[i], low[j])
if seen[i] <= low[j]:
cut[i] += i != root or children > 1
root = 1
tarjan(root)
seen_cut = set()
res = []
done = [0] * n
def dfs2(i):
done[i] = 1
min_cost = cost[i]
for j in G[i]:
if done[j]: continue
if cut[j]:
seen_cut.add(j)
continue
min_cost = min(min_cost, dfs2(j))
return min_cost
for i in range(n):
if done[i] or cut[i]: continue
seen_cut = set()
min_cost = dfs2(i)
if len(seen_cut) < 2:
res.append(min_cost)
return sum(res) - max(res) if len(res) > 1 else res[0]
python3 解法, 执行用时: 1672 ms, 内存消耗: 143.9 MB, 提交时间: 2023-10-26 23:49:15
class Solution:
def minimumCost(self, cost: List[int], roads: List[List[int]]) -> int:
n = len(cost)
adjMap = defaultdict(set)
for u, v in roads:
adjMap[u].add(v)
adjMap[v].add(u)
# 找VBCC和割点
VBCCId, VBCCGroup, VBCCIdByNode = Tarjan.getVBCC(n, adjMap)
cuttingPoints = set(i for i in range(n) if len(VBCCIdByNode[i]) > 1)
# 统计连通分量里包含几个原图的割点，不能选连了两个以上个点的分量
counter = [sum(node in cuttingPoints for node in VBCCGroup[i]) for i in range(VBCCId)]
goodGroups = [i for i in range(VBCCId) if counter[i] <= 1]
# 不能选割点
costs = [min(cost[v] for v in VBCCGroup[k] if v not in cuttingPoints) for k in goodGroups]
return costs[0] if len(costs) == 1 else sum(costs) - max(costs)
# Tarjan 各个算法模板
class Tarjan:
INF = int(1e20)
@staticmethod
def getSCC(
n: int, adjMap: DefaultDict[int, Set[int]]
) -> Tuple[int, DefaultDict[int, Set[int]], List[int]]:
"""Tarjan求解有向图的强连通分量
Args:
n (int): 结点0-n-1
adjMap (DefaultDict[int, Set[int]]): 图
Returns:
Tuple[int, DefaultDict[int, Set[int]], List[int]]: SCC的数量、分组、每个结点对应的SCC编号
"""
def dfs(cur: int) -> None:
nonlocal dfsId, SCCId
if visited[cur]:
return
visited[cur] = True
order[cur] = low[cur] = dfsId
dfsId += 1
stack.append(cur)
inStack[cur] = True
for next in adjMap[cur]:
if not visited[next]:
dfs(next)
low[cur] = min(low[cur], low[next])
elif inStack[next]:
low[cur] = min(low[cur], order[next]) # 注意这里是order
if order[cur] == low[cur]:
while stack:
top = stack.pop()
inStack[top] = False
SCCGroupById[SCCId].add(top)
SCCIdByNode[top] = SCCId
if top == cur:
break
SCCId += 1
dfsId = 0
order, low = [Tarjan.INF] * n, [Tarjan.INF] * n
visited = [False] * n
stack = []
inStack = [False] * n
SCCId = 0
SCCGroupById = defaultdict(set)
SCCIdByNode = [-1] * n
for cur in range(n):
if not visited[cur]:
dfs(cur)
return SCCId, SCCGroupById, SCCIdByNode
@staticmethod
def getCuttingPointAndCuttingEdge(
n: int, adjMap: DefaultDict[int, Set[int]]
) -> Tuple[Set[int], Set[Tuple[int, int]]]:
"""Tarjan求解无向图的割点和割边(桥)
Args:
n (int): 结点0-n-1
adjMap (DefaultDict[int, Set[int]]): 图
Returns:
Tuple[Set[int], Set[Tuple[int, int]]]: 割点、桥
- 边对 (u,v) 中 u < v
"""
def dfs(cur: int, parent: int) -> None:
nonlocal dfsId
if visited[cur]:
return
visited[cur] = True
order[cur] = low[cur] = dfsId
dfsId += 1
dfsChild = 0
for next in adjMap[cur]:
if next == parent:
continue
if not visited[next]:
dfsChild += 1
dfs(next, cur)
low[cur] = min(low[cur], low[next])
if low[next] > order[cur]:
cuttingEdge.add(tuple(sorted([cur, next])))
if parent != -1 and low[next] >= order[cur]:
cuttingPoint.add(cur)
elif parent == -1 and dfsChild > 1: # 出发点没有祖先啊，所以特判一下
cuttingPoint.add(cur)
else:
low[cur] = min(low[cur], order[next]) # 注意这里是order
dfsId = 0
order, low = [Tarjan.INF] * n, [Tarjan.INF] * n
visited = [False] * n
cuttingPoint = set()
cuttingEdge = set()
for i in range(n):
if not visited[i]:
dfs(i, -1)
return cuttingPoint, cuttingEdge
@staticmethod
def getVBCC(
n: int, adjMap: DefaultDict[int, Set[int]]
) -> Tuple[int, DefaultDict[int, Set[int]], List[Set[int]]]:
"""Tarjan求解无向图的点双联通分量
Args:
n (int): 结点0-n-1
adjMap (DefaultDict[int, Set[int]]): 图
Returns:
Tuple[int, DefaultDict[int, Set[int]], List[Set[int]]]: VBCC的数量、分组、每个结点对应的VBCC编号
- 我们将深搜时遇到的所有边加入到栈里面，
当找到一个割点的时候，
就将这个割点往下走到的所有边弹出，
而这些边所连接的点就是一个点双了
- 两个点和一条边构成的图也称为(V)BCC,因为两个点均不为割点
- VBCC编号多余1个的都是割点
"""
def dfs(cur: int, parent: int) -> None:
nonlocal dfsId, VBCCId
if visited[cur]:
return
visited[cur] = True
order[cur] = low[cur] = dfsId
dfsId += 1
dfsChild = 0
for next in adjMap[cur]:
if next == parent:
continue
if not visited[next]:
dfsChild += 1
stack.append((cur, next))
dfs(next, cur)
low[cur] = min(low[cur], low[next])
# 遇到了割点(根和非根两种)
if (parent == -1 and dfsChild > 1) or (
parent != -1 and low[next] >= order[cur]
):
while stack:
top = stack.pop()
VBCCGroupById[VBCCId].add(top[0])
VBCCGroupById[VBCCId].add(top[1])
VBCCIdByNode[top[0]].add(VBCCId)
VBCCIdByNode[top[1]].add(VBCCId)
if top == (cur, next):
break
VBCCId += 1
elif low[cur] > order[next]:
low[cur] = min(low[cur], order[next])
stack.append((cur, next))
dfsId = 0
order, low = [Tarjan.INF] * n, [Tarjan.INF] * n
visited = [False] * n
stack = []
VBCCId = 0 # 点双个数
VBCCGroupById = defaultdict(set) # 每个点双包含哪些点
VBCCIdByNode = [set() for _ in range(n)] # 每个点属于哪一(几)个点双，属于多个点双的点就是割点
for cur in range(n):
if not visited[cur]:
dfs(cur, -1)
if stack:
while stack:
top = stack.pop()
VBCCGroupById[VBCCId].add(top[0])
VBCCGroupById[VBCCId].add(top[1])
VBCCIdByNode[top[0]].add(VBCCId)
VBCCIdByNode[top[1]].add(VBCCId)
VBCCId += 1
return VBCCId, VBCCGroupById, VBCCIdByNode
@staticmethod
def getEBCC(
n: int, adjMap: DefaultDict[int, Set[int]]
) -> Tuple[int, DefaultDict[int, Set[Tuple[int, int]]], DefaultDict[Tuple[int, int], int]]:
"""Tarjan求解无向图的边双联通分量
Args:
n (int): 结点0-n-1
adjMap (DefaultDict[int, Set[int]]): 图
Returns:
Tuple[int, DefaultDict[int, Set[Tuple[int, int]]], DefaultDict[Tuple[int, int], int]]]: EBCC的数量、分组、每条边对应的EBCC编号
- 边对 (u,v) 中 u < v
- 实现思路：
- 将所有的割边删掉剩下的都是边连通分量了(其实可以用并查集做)
- 处理出割边,再对整个无向图进行一次DFS,对于节点cur的出边(cur,next),如果它是割边,则跳过这条边不沿着它往下走
"""
def dfs(cur: int, parent: int) -> None:
nonlocal EBCCId
if visited[cur]:
return
visited[cur] = True
for next in adjMap[cur]:
if next == parent:
continue
edge = tuple(sorted([cur, next]))
if edge in cuttingEdges:
continue
EBCCGroupById[EBCCId].add(edge)
EBCCIdByEdge[edge] = EBCCId
dfs(next, cur)
_, cuttingEdges = Tarjan.getCuttingPointAndCuttingEdge(n, adjMap)
visited = [False] * n
EBCCId = 0 # 边双个数
EBCCGroupById = defaultdict(set) # 每个边双包含哪些边
EBCCIdByEdge = defaultdict(int) # 每条边属于哪一个边双
for cur in range(n):
if not visited[cur]:
dfs(cur, -1)
EBCCId += 1
for edge in cuttingEdges:
EBCCGroupById[EBCCId].add(edge)
EBCCIdByEdge[edge] = EBCCId
EBCCId += 1
return EBCCId, EBCCGroupById, EBCCIdByEdge
java 解法, 执行用时: 154 ms, 内存消耗: 96.1 MB, 提交时间: 2023-10-26 23:48:32
class Solution {
private static final int S = 0;
private Map<Integer, List<Integer>> adj;
private boolean[] isCut;
private int[] dfn;
private int[] low;
private int clk;
private Deque<Integer> stk;
private LinkedList<List<Integer>> dcc;
// https://leetcode.cn/problems/s5kipK/solution/by-tsreaper-z8by/
public long minimumCost(int[] cost, int[][] roads) {
int n = cost.length;
if (n == 1) {
return cost[0];
}
adj = new HashMap<>();
for (int[] road : roads) {
adj.computeIfAbsent(road[0], key -> new ArrayList<>()).add(road[1]);
adj.computeIfAbsent(road[1], key -> new ArrayList<>()).add(road[0]);
}
isCut = new boolean[n];
dfn = new int[n];
low = new int[n];
clk = 0;
stk = new ArrayDeque<>();
dcc = new LinkedList<>();
tarjan(S);
// 整张图是一个双连通分量，选择整张图权值最小的点即可
if (dcc.size() == 1) {
return Arrays.stream(cost).min().orElseThrow();
}
List<Integer> vec = new ArrayList<>();
for (List<Integer> c : dcc) {
int cnt = 0;
int min = Integer.MAX_VALUE;
for (int x : c) {
if (isCut[x]) {
cnt++;
} else {
min = Math.min(min, cost[x]);
}
}
// 该双连通分量只和一个割点相连，是缩点形成的树的叶子节点
if (cnt == 1) {
vec.add(min);
}
}
Collections.sort(vec);
long res = 0;
for (int i = 0; i < vec.size() - 1; i++) {
res += vec.get(i);
}
return res;
}
private void tarjan(int sn) {
dfn[sn] = low[sn] = ++clk;
stk.push(sn);
int flag = 0;
for (int fn : adj.getOrDefault(sn, new ArrayList<>())) {
if (dfn[fn] == 0) {
tarjan(fn);
low[sn] = Math.min(low[sn], low[fn]);
if (low[fn] >= dfn[sn]) {
flag++;
if (sn != S || flag > 1) {
isCut[sn] = true;
}
int t;
dcc.add(new ArrayList<>());
do {
t = stk.pop();
dcc.getLast().add(t);
} while (t != fn);
dcc.getLast().add(sn);
}
} else {
low[sn] = Math.min(low[sn], dfn[fn]);
}
}
}
}
cpp 解法, 执行用时: 948 ms, 内存消耗: 249.4 MB, 提交时间: 2023-10-26 23:48:10
class Solution {
const int S = 0;
int n;
vector<vector<int>> e;
vector<bool> isCut;
vector<int> dfn, low;
int clk = 0;
stack<int> stk;
// 所有点双连通分量
vector<vector<int>> dcc;
void tarjan(int sn) {
dfn[sn] = low[sn] = ++clk;
stk.push(sn);
int flag = 0;
for (int fn : e[sn]) {
if (!dfn[fn]) {
tarjan(fn);
low[sn] = min(low[sn], low[fn]);
if (low[fn] >= dfn[sn]) {
flag++;
if (sn != S || flag > 1) isCut[sn] = true;
int t;
dcc.push_back(vector<int>());
do {
t = stk.top(); stk.pop();
dcc.back().push_back(t);
} while (t != fn);
dcc.back().push_back(sn);
}
} else low[sn] = min(low[sn], dfn[fn]);
}
}
public:
long long minimumCost(vector<int>& cost, vector<vector<int>>& roads) {
n = cost.size();
if (n == 1) return cost[0];
e = vector<vector<int>>(n);
for (auto &r : roads) e[r[0]].push_back(r[1]), e[r[1]].push_back(r[0]);
isCut = vector<bool>(n);
dfn = low = vector<int>(n);
tarjan(S);
// 整张图是一个双连通分量，选择整张图权值最小的点即可
if (dcc.size() == 1) {
int ans = 2e9;
for (int x : cost) ans = min(ans, x);
return ans;
}
vector<int> vec;
for (auto &c : dcc) {
int cnt = 0, mn = 2e9;
for (int x : c) {
if (isCut[x]) cnt++;
else mn = min(mn, cost[x]);
}
// 该双连通分量只和一个割点相连，是缩点形成的树的叶子节点
if (cnt == 1) vec.push_back(mn);
}
sort(vec.begin(), vec.end());
long long ans = 0;
for (int i = 0; i + 1 < vec.size(); i++) ans += vec[i];
return ans;
}
};
{:height=170px}
{:height=60px}