【Day 77 】2021-11-25 - 924. 尽量减少恶意软件的传播 #96
Comments
思路:本题是根据提供的edge的关系，构建图中的若干连通分量。
代码:实现语言: C++ class Solution {
vector<int> Father, sz, pc; // pc (point count): 连通块中一共有多少个被感染的点
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial)
{
const int n = graph.size();
for (int i = 0; i < n; i++)
{
Father.push_back(i);
sz.push_back(1);
pc.push_back(0); // 一开始每个连通块都没有被感染的点
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) /* 将所有连通的集合合并 */
if (graph[i][j] && find(i) != find(j)) /* i, j之间有边, 但不在一个连通块内 */
{
sz[find(i)] += sz[find(j)];
Father[find(j)] = find(i);
}
for (auto& x : initial)
pc[find(x)]++;
int rs = -1, rp = INT_MAX; // rs: 可以被拯救的点数, rp: 结点的编号
for (auto& x : initial)
{
if (rs == -1)
rp = min(rp, x); /* 如果没有选择过任意一个点的话, 可以随便选一个点 */
if (pc[find(x)] == 1) // 当前连通块只包含1个被感染的点的话
{
if (rs < sz[find(x)]) // rs 不如当前的点好的话
{
rs = sz[find(x)];
rp = x;
}
else if (rs == sz[find(x)])
{
rp = min(rp, x); /* 取编号最小的一个点 */
}
}
}
return rp;
}
int find(int x)
{
if (Father[x] != x)
Father[x] = find(Father[x]);
return Father[x];
}
};复杂度分析:时间复杂度
空间复杂度
|
思路
关键点代码
C++ Code: class UF
{
vector<int> parent;
vector<int> weight;
int count;
public:
UF(int n)
{
for(int i=0; i< n; i++)
{
parent.push_back(i);
weight.push_back(1);
}
count = n;
}
void uninTwoNode(int i, int j)
{
int parentI = findParent(i);
int parentJ = findParent(j);
if(parentI != parentJ)
{
if(weight[parentI] < weight[parentJ])
{
parent[parentI] = parentJ;
weight[parentJ] += weight[parentI];
weight[parentI]=0 ;
count --;
}
else
{
parent[parentJ] = parentI;
weight[parentI] += weight[parentJ];
weight[parentJ]=0;
count--;
}
}
}
int findParent(int i)
{
while(parent[i]!=i)
{
parent[i] = parent[parent[i]];
i = parent[i];
}
return i;
}
int getWeight(int i)
{
return weight[i];
}
};
class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
UF uf(graph.size());
for(int i=0; i< graph.size(); i++)
{
for(int j=i+1; j< graph[i].size(); j++)
{
if(graph[i][j])
uf.uninTwoNode(i, j);
}
}
unordered_map<int, int> record;
sort(initial.begin(), initial.end());
int totalEffectNode =0;
for(int i=0; i< initial.size(); i++)
{
int rootNode =uf.findParent(initial[i]);
record[rootNode]++;
if(record[rootNode]==1)
{
totalEffectNode += uf.getWeight(rootNode);
}
}
int minNum =INT_MAX;
int ret =-1;
for(int i=0; i< initial.size(); i++)
{
int rootNode = uf.findParent(initial[i]);
if(record[rootNode]==1)
{
int effectNode = totalEffectNode - uf.getWeight(rootNode);
if(effectNode<minNum)
{
minNum = effectNode; ;
ret = initial[i];
}
}
else
{
if(totalEffectNode < minNum)
{
minNum = totalEffectNode;
ret =initial[i];
}
}
}
return ret;
}
};
|
class Solution:
def minMalwareSpread(self, graph, initial):
def dfs(i):
nodes.add(i)
for j in range(len(graph[i])):
if graph[i][j] and j not in nodes:
dfs(j)
rank, initial = collections.defaultdict(list), set(initial)
for node in sorted(initial):
nodes = set()
dfs(node)
if nodes & initial == {node}:
rank[len(nodes)].append(node)
return rank[max(rank)][0] if rank else min(initial) |
代码
C++ Code: struct node{
int parent;
int bad;
int connect;
node(int x) : parent(x), bad(0), connect(1) {}
};
class Solution {
public:
vector<node*> parents;
int find(int x)
{
if(x!=parents[x]->parent)
return find(parents[x]->parent);
return x;
}
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
for(int i=0;i<n;i++)
{
parents.push_back(new node(i));
}
int m = initial.size();
int min_idx = n;
for(int i=0;i<m;i++)
{
parents[initial[i]]->bad = 1;
min_idx = min(min_idx,initial[i]);
}
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(graph[i][j]==1&&find(i)!=find(j))
{
int p_j = find(j);
int p_i = find(i);
parents[p_i]->parent = p_j;
parents[p_j]->connect += parents[p_i]->connect;
parents[p_j]->bad += parents[p_i]->bad;
}
int max_connect = 0;
for(int i=0;i<m;i++)
{
int p = find(initial[i]);
if(parents[p]->bad<2)
{
if(parents[p]->connect>max_connect)
{
max_connect = parents[p]->connect;
min_idx = initial[i];
}
else if(parents[p]->connect==max_connect&&min_idx>initial[i])
min_idx = initial[i];
}
}
return min_idx;
}
};
|
|
class Solution { }; |
Idea:Union Find Code:class UnionFind():
def __init__(self, N):
self.p = {}
self.sz = {}
for i in range(N):
self.p[i] = i
self.sz[i] = 1
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, x, y):
xr = self.find(x)
yr = self.find(y)
self.p[xr] = yr
self.sz[yr] += self.sz[xr]
def size(self, x):
return self.sz[self.find(x)]
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
UF = UnionFind(len(initial))
for i in range(len(graph)):
for j in range(i):
if graph[i][j]:
UF.union(i, j)
count = collections.Counter(UF.find(u) for u in initial)
ans = (-1, min(initial))
for node in initial:
root = UF.find(node)
if count[root] == 1:
if UF.size(root) > ans[0]:
ans = UF.size(root), node
elif UF.size(root) == ans[0] and node < ans[1]:
ans = UF.size(root), node
return ans[1]Complexity:Time: O(N ^2) |
class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int len = graph.length;
UnionFind union = new UnionFind();
union.init(len);
for(int i = 0; i < len; i++) {
for(int j = i+1; j < len; j++) {
if(graph[i][j] == 1) {
union.merge(i, j);
}
}
}
// 如果有多个节点满足条件，就返回索引最小的节点。 因此需要先对 initial 排序
Arrays.sort(initial);
int res = initial[0];
int max = 0; // 记录集合的联通块数最大的集合大小
for(int i = 0; i < initial.length; i++) {
int root = union.find(initial[i]);
boolean notOnly = false;
for(int j = 0; j < initial.length; j++) {
if(i == j) {
continue;
}
if(union.find(initial[j]) == root) {
notOnly = true;
break;
}
}
if(!notOnly) {
int count = 0;
for(int k = 0; k < len; k++) {
if(union.find(k) == root) {
count++;
}
}
// 此节点所属的联通块数是目前最大的集合，则更新 max 的值。
if(count > max) {
max = count;
res = initial[i];
}
}
}
return res;
}
private class UnionFind {
private int[] parent;
private int[] rank; // 记录每个根节点对应的树的深度
private void init(int len) {
this.parent = new int[len];
this.rank = new int[len];
for(int i = 0; i < len; ++i) {
parent[i] = i;
rank[i] = 1;
}
}
// 路径压缩 把沿途的每个节点的父节点都设为根节点
private int find(int x) {
return x == parent[x] ? parent[x] : (parent[x] = find(parent[x]));
}
private void merge(int x, int y) {
int xroot = find(x); //先找到两个根节点
int yroot = find(y);
if(xroot == yroot) {
return;
}
// 合并时比较两个根节点，把rank较小者往较大者上合并
if(rank[xroot] <= rank[yroot]) {
parent[xroot] = yroot;
} else {
parent[yroot] = xroot;
}
if(rank[xroot] == rank[yroot]) {
rank[yroot]++; // //如果深度相同且根节点不同，则新的根节点的深度+1
}
}
}
} |
class Solution(object):
def minMalwareSpread(self, graph, initial):
"""
:type graph: List[List[int]]
:type initial: List[int]
:rtype: int
"""
initial, seen = set(initial), set()
counts = {}
for node in initial:
if node not in seen:
initial_count, node_count = self.dfs(graph, node, seen, initial)
if initial_count == 1:
counts[node] = node_count
if len(counts) > 0:
# maximize count then minimize node index
_, neg_n = max((c, -n) for n, c in counts.items())
return -neg_n
else:
return min(initial)
def dfs(self, graph, node, seeing, initial):
if node in seeing:
return 0, 0
seeing.add(node)
initial_count, node_count = node in initial, 1
for n in range(len(graph)):
if graph[node][n] == 1:
i, n = self.dfs(graph, n, seeing, initial)
initial_count += i
node_count += n
return initial_count, node_count |
|
染色法 class UF:
def __init__(self):
self.parent = {}
self.size = defaultdict(lambda: 1)
def find(self, x):
#Don't foget this one, this is mandatory as lazy init.
ox = x
self.parent.setdefault(x, x)
while x != self.parent[x]:
x = self.parent[x]
self.parent[ox] = x
return x
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py: return
if self.size[px] < self.size[py]:
self.parent[px] = py
self.size[py] += self.size[px]
else:
self.parent[py] = px
self.size[px] += self.size[py]
def is_connected(self, x, y):
return self.find(x) == self.find(y)
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
uf = UF()
M, N = len(graph), len(graph[0])
color = {}
for i in range(M):
for j in range(N):
if graph[i][j] == 1:
uf.union(i, j)
color_cnt = defaultdict(int)
for u in initial:
px = uf.find(u)
count = collections.Counter(uf.find(u) for u in initial)
ans = (-1, min(initial))
for u in initial:
p = uf.find(u)
if count[p] == 1: # unique color
if uf.size[p] > ans[0]:
ans = uf.size[p], u
elif uf.size[p] == ans[0] and u < ans[1]:
ans = uf.size[p], u
return ans[1] |
Idea:basically we need to find out the connected component which the node in innital belongs to, return the connected component with the largest size. If two nodes in innitial belong to the same connected component, those two nodes aren't the answer, because deleting any one won't change the spread of malware. Therefore, we can use union find to find the root of each node in innital, count the frequency of each root. Then focus on node that has unique root. Find out the size of connected component of each such root, the one with maximum size is the answer. If no node has unique root, we just return the minimum node. Complexity:Time: O(n^2) //create unionfind class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
UF uf = new UF(n);
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
if(graph[i][j]==1) {
uf.union(i,j);
}
}
}
int[] count = new int[n];
for(int node: initial) {
count[uf.find(node)]++;
}
int ans=-1, ansSize=-1;
for(int node: initial) {
int root = uf.find(node);
if(count[root]==1) {
int currSize = uf.getSize(root);
if(currSize>ansSize) {
ansSize=currSize;
ans=node;
}
else if(currSize == ansSize && node < ans) {
ans=node;
}
}
}
if(ans==-1) {
ans=n+1;
for(int node: initial) {
ans = Math.min(node,ans);
}
}
return ans;
}
class UF {
int[] parent;
int[] size;
public UF(int n) {
parent = new int[n];
size = new int[n];
for(int i=0;i<n;i++) {
parent[i]=i;
size[i]=1;
}
}
public int find(int x) {
while(parent[x]!=x) {
parent[x]=parent[parent[x]];
x=parent[x];
}
return parent[x];
}
public int getSize(int x) {
return size[find(x)];
}
public void union(int x, int y) {
int xroot = find(x);
int yroot = find(y);
if(xroot!=yroot) {
if(size[xroot]>size[yroot]) {
parent[yroot]=xroot;
size[xroot]+=size[yroot];
}
else {
parent[xroot]=yroot;
size[yroot]+=size[xroot];
}
}
}
}
} |
Open
class Solution:
def minMalwareSpread(self, graph, initial) -> int:
self.n = len(graph)
self.graph = graph
self.initial = sorted(initial)
self.colors = [0] * self.n
self.cur_color = 1
for i in range(self.n):
if self.colors[i] == 0:
self.dfs(i,self.cur_color)
self.cur_color += 1
counts = [0] * self.cur_color
for node in initial:
counts[self.colors[node]] += 1
maybe = []
for node in initial:
if counts[self.colors[node]] == 1:
maybe.append(node)
counts = [0] * self.cur_color
for i in range(self.n):
counts[self.colors[i]] += 1
res = -1
maxCount = -1
for node in maybe:
if (counts[self.colors[node]] > maxCount):
maxCount = counts[self.colors[node]]
res = node
if res == -1:
res = min(initial)
return res
def dfs(self, node, color):
self.colors[node] = self.cur_color
for j in range(self.n):
if self.colors[j] != 0:
continue
if self.graph[node][j] != 1:
continue
self.dfs(j, self.cur_color) |
# union find
# union all connected nodes
# for every parent count how many infected nodes the union has
# if there are more than 1 infected nodes, removing any of it will do nothing
# else choose the node from initial that has the biggest size in union
# time: O(N^2)
# space: O(N)
class UF:
def __init__(self, n):
self.size = {}
self.parent = {}
# count of mal nodes of parent
self.count = {}
for i in range(n):
self.parent[i] = i
self.size[i] = 1
self.count[i] = 0
def add_count(self, x):
self.count[x] += 1
def find(self, x):
if self.parent[x] != x:
parent = self.parent[x]
self.parent[x] = parent
return self.find(parent)
return x
def is_connected(self, x, y):
return self.find(x) == self.find(y)
def union(self, x, y):
if self.is_connected(x, y): return
x_parent = self.find(x)
y_parent = self.find(y)
if self.size[x_parent] < self.size[y_parent]:
self.parent[x_parent] = y_parent
self.size[y_parent] += self.size[x_parent]
else:
self.parent[y_parent] = x_parent
self.size[x_parent] += self.size[y_parent]
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
n = len(graph)
union_find = UF(n)
for i in range(n):
for j in range(n):
if i == j: continue
if graph[i][j] == 1:
union_find.union(i, j)
mal_parents = []
for mal in initial:
parent = union_find.find(mal)
mal_parents.append(parent)
union_find.add_count(parent)
max_infected = -1
max_infected_node = -1
for i, mal in enumerate(initial):
parent = mal_parents[i]
curr_infected = union_find.size[parent]
infected_count = union_find.count[parent]
# remove this node will have it be infected again by other connected mal(s)
if infected_count > 1:
curr_infected = 0
if curr_infected > max_infected:
max_infected = curr_infected
max_infected_node = mal
# pick the smallest node
elif curr_infected == max_infected and mal < max_infected_node:
max_infected_node = mal
return max_infected_node |
|
有点难了, 先mark 一下抄个答案. 大概思路就是查并集, 这个答案是n 次查询, 可以通过优化改成一个查询 class DJset {
public:
vector<int> parent;
vector<int> rank;
vector<int> size;
DJset(int n): parent(n), rank(n), size(n, 1) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void merge(int x, int y) {
int rx = find(x);
int ry = find(y);
if (rx != ry) {
if (rank[rx] < rank[ry]) swap(rx, ry);
parent[ry] = rx;
size[rx] += size[ry];
size[ry] = 0;
if (rank[rx] == rank[ry]) rank[rx] += 1;
}
}
};
class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
sort(initial.begin(), initial.end());
int minM = n; // 记录最少感染节点数
int idx = initial[0]; // 记录产生最少感染节点数的 删除节点
// 计算在删除 e 节点的条件下，有多少个节点被感染
for (auto& e : initial) {
int M = 0;
DJset ds(n);
// 重构并查集
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (graph[i][j] == 1) ds.merge(i, j);
}
}
// 计算重构之后的感染节点数
unordered_set<int> seen;
for (auto& i : initial) {
if (i == e) continue;
int ri = ds.find(i);
if (seen.count(ri)) continue;
seen.insert(ri);
M += ds.size[ri];
}
if (M < minM) {
minM = M;
idx = e;
}
}
return idx;
}
}; |
思路
Java Codeclass Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
Arrays.sort(initial);
UF uf = new UF(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] == 1) {
uf.union(i, j);
}
}
}
int[] countMap = new int[n]; // each parent to final infected nodes count
for (int i = 0; i < n; i++) {
countMap[uf.find(i)]++;
}
Map<Integer, List<Integer>> infectedMap = new HashMap(); //each parent to its init infection nodes
for (int i : initial) {
infectedMap.computeIfAbsent(uf.find(i), x -> new ArrayList()).add(i);
}
int res = -1;
int maxSize = 0;
for (int x : infectedMap.keySet()) {
if (infectedMap.get(x).size() == 1) {
if (maxSize < countMap[uf.find(x)]) {
maxSize = countMap[uf.find(x)];
res = infectedMap.get(x).get(0);
} else if (maxSize == countMap[uf.find(x)]) {
res = Math.min(res, infectedMap.get(x).get(0));
}
}
}
return res == -1 ? initial[0] : res;
}
private static class UF {
int[] parent;
public UF(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int pX = find(x);
int pY = find(y);
if (pX != pY) {
parent[y] = x;
}
}
}
} |
|
参考标准答案 T: O(N^2) |
|
方法 实现语言: C++
class Solution {
vector<int> Father, sz, pc; // pc (point count):
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial)
{
const int n = graph.size();
for (int i = 0; i < n; i++)
{
Father.push_back(i);
sz.push_back(1);
pc.push_back(0);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (graph[i][j] && find(i) != find(j))
{
sz[find(i)] += sz[find(j)];
Father[find(j)] = find(i);
}
for (auto& x : initial)
pc[find(x)]++;
int rs = -1, rp = INT_MAX;
for (auto& x : initial)
{
if (rs == -1)
rp = min(rp, x);
if (pc[find(x)] == 1)
{
if (rs < sz[find(x)])
{
rs = sz[find(x)];
rp = x;
}
else if (rs == sz[find(x)])
{
rp = min(rp, x);
}
}
}
return rp;
}
int find(int x)
{
if (Father[x] != x)
Father[x] = find(Father[x]);
return Father[x];
}
};复杂度分析 |
思路DFS 代码JavaScript Code var minMalwareSpread = function (graph, initial) {
const N = graph.length;
initial.sort((a, b) => a - b);
let colors = Array.from({ length: N }).fill(0);
let curColor = 1;
// 给联通分量标色
for (let i = 0; i < N; i++) {
if (colors[i] === 0) {
dfs(i, curColor++);
}
}
let counts = Array.from({ length: curColor }).fill(0);
for (node of initial) {
counts[colors[node]]++;
}
let maybe = [];
for (node of initial) {
if (counts[colors[node]] === 1) {
maybe.push(node);
}
}
counts.fill(0);
for (let i = 0; i < N; i++) {
counts[colors[i]]++;
}
let res = -1;
let maxCount = -1;
for (let node of maybe) {
if (counts[colors[node]] > maxCount) {
maxCount = counts[colors[node]];
res = node;
}
}
if (res === -1) {
res = Math.min(...initial);
}
return res;
function dfs(start, color) {
colors[start] = color;
for (let i = 0; i < N; i++) {
if (graph[start][i] === 1 && colors[i] === 0) {
dfs(i, color);
}
}
}
};复杂度
|
代码class UnionFind:
def __init__(self):
self.father = {}
self.size = {}
def find(self, x):
self.father.setdefault(x, x)
if x != self.father[x]:
self.father[x] = self.find(self.father[x])
return self.father[x]
def union(self, x, y):
fx, fy = self.find(x), self.find(y)
if self.size.setdefault(fx, 1) < self.size.setdefault(fy, 1):
self.father[fx] = fy
self.size[fy] += self.size[fx]
elif fx != fy:
self.father[fy] = fx
self.size[fx] += self.size[fy]
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
uf = UnionFind()
for i in range(len(graph)):
for j in range(i, len(graph)):
if graph[i][j]:
uf.union(i, j)
initial.sort()
max_size, index, fi = 0, -1, []
cnt = collections.defaultdict(int)
for init in initial:
fi.append(uf.find(init))
cnt[fi[-1]] += 1
for i in range(len(initial)):
if cnt[fi[i]] > 1:
continue
if uf.size[fi[i]] > max_size:
max_size = uf.size[fi[i]]
index = initial[i]
return index if index != -1 else initial[0] |
|
##思想 代码class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int N = graph.length;
DSU dsu = new DSU(N);
for (int i = 0; i < N; ++i)
for (int j = i+1; j < N; ++j)
if (graph[i][j] == 1)
dsu.union(i, j);
int[] count = new int[N];
for (int node: initial)
count[dsu.find(node)]++;
int ans = -1, ansSize = -1;
for (int node: initial) {
int root = dsu.find(node);
if (count[root] == 1) { // unique color
int rootSize = dsu.size(root);
if (rootSize > ansSize) {
ansSize = rootSize;
ans = node;
} else if (rootSize == ansSize && node < ans) {
ansSize = rootSize;
ans = node;
}
}
}
if (ans == -1) {
ans = Integer.MAX_VALUE;
for (int node: initial)
ans = Math.min(ans, node);
}
return ans;
}
}
class DSU {
int[] p, sz;
DSU(int N) {
p = new int[N];
for (int x = 0; x < N; ++x)
p[x] = x;
sz = new int[N];
Arrays.fill(sz, 1);
}
public int find(int x) {
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
public void union(int x, int y) {
int xr = find(x);
int yr = find(y);
p[xr] = yr;
sz[yr] += sz[xr];
}
public int size(int x) {
return sz[find(x)];
}
}复杂度
|
思路
代码class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int N = graph.length;
DSU dsu = new DSU(N);
for(int i = 0;i < N;i++){
for(int j = i+1;j < N;j++){
if(graph[i][j] == 1){
dsu.union(i, j);
}
}
}
int[] count = new int[N];
for(int node: initial){
count[dsu.find(node)]++;
}
int ans = -1, ansSize = -1;
for(int node: initial){
int root = dsu.find(node);
if(count[root] == 1) {
int rootSize = dsu.size(root);
if(rootSize > ansSize) {
ansSize = rootSize;
ans = node;
} else if(rootSize == ansSize && node < ans){
ansSize = rootSize;
ans = node;
}
}
}
if(ans == -1){
ans = Integer.MAX_VALUE;
for(int node: initial){
ans = Math.min(ans, node);
}
}
return ans;
}
}
class DSU{
int[] p, sz;
DSU(int N) {
p = new int[N];
for(int x = 0;x < N;x++){
p[x] = x;
}
sz = new int[N];
Arrays.fill(sz, 1);
}
public int find(int x){
if(p[x] != x){
p[x] = find(p[x]);
}
return p[x];
}
public void union(int x, int y){
int xr = find(x);
int yr = find(y);
p[xr] = yr;
sz[yr] += sz[xr];
}
public int size(int x) {
return sz[find(x)];
}
}复杂度time: O(N^2) |
思路使用并查集的方法 先将所有联通的 node 在并查集中根据 graph 的 edges 联通, 然后在并查集中加入 size, 每次 union 的时候额外记录每个联通分量的大小 之后对于所有 initial 中的节点, 统计 每个 parent node pi 对应的 initial 的节点个数, 用一个 list 存储起来 遍历所有的 parent, list of initial node pairs, 如果 list of initials size 大于 1, 代表即使移除了一个点, 也会被另一个点感染, 所以可以直接跳过直到最后, 如果全部都 大于 1, 那么就选 initial 里面 index 最小的 return, 因为无法 减小感染, 否则在过程中会被 等于 1 的情况覆盖掉 如果 list of initials size 等于 1 的情况 如果 cur_size 等于 1, 并且这个联通分量的大小大于之前最大的联通分量的大小, 那么应该删除这个 initial 点, 所以更新 size 为这个的 size 并且更新 index 为这个 initial 的 index 如果等于 1 并且 这个联通分量的大小跟之前最大的联通分量的大小相同, 那么取两个中 index 更小的作为 index from collections import defaultdict
class UF:
def __init__(self, num):
self.parents = [i for i in range(num)]
self.size = [1 for _ in range(num)]
def find(self, x):
while self.parents[x] != x:
self.parents[x] = self.parents[self.parents[x]]
x = self.parents[x]
return x
def connect(self, x, y):
if self.find(x) != self.find(y):
px, py = self.find(x), self.find(y)
self.parents[px] = py
self.size[py] += self.size[px]
self.size[px] = 0
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
l = len(graph)
uf = UF(l)
for i in range(l):
g = graph[i]
for j in range(i, l):
if g[j] == 1:
uf.connect(i, j)
pis = defaultdict(list)
for i in initial:
pi = uf.find(i)
pis[pi].append(i)
size = -1
index = float('inf')
for k, v in pis.items():
if len(v) > 1:
cur_size = 0
cur_index = min(v)
else:
cur_size = uf.size[k]
cur_index = v[0]
if cur_size == size:
index = min(cur_index, index)
elif cur_size > size:
index = cur_index
size = cur_size
return index复杂度n 为 graph 中节点数目 时间复杂度: O(n^2) 遍历图构建 uf 复杂度是 O(n^2) 遍历 构建 parents node 和 遍历找到 index 复杂度为 O(n) 空间复杂度: O(n) 并查集的空间复杂度 |
type UnionFindSet struct {
Parents []int //记录每个节点的上级
Size []int // 记录以当前结点为顶点的连通分量里面的节点有多少个（只有自己的话，值为1）
}
func (u *UnionFindSet) Init(size int) {
u.Parents = make([]int, size)
u.Size = make([]int, size)
for i := 0; i < size; i++ {
u.Parents[i] = i
u.Size[i] = 1
}
}
func (u *UnionFindSet) Find(node int) int {
if u.Parents[node] == node {
return node
}
root := u.Find(u.Parents[node])
u.Parents[node] = root
return root
}
func (u *UnionFindSet) Union(node1 int, node2 int) {
root1 := u.Find(node1)
root2 := u.Find(node2)
if root1 == root2 {
return
}
if root1 < root2 {
u.Parents[root1] = root2
u.Size[root2] += u.Size[root1] // 以root2为最顶层结点的连通分量的个数要叠加上root1的
}
}
func minMalwareSpread(graph [][]int, initial []int) int {
// 初始化并查集
u := &UnionFindSet{}
u.Init(len(graph))
// 根据graph进行连通，生成连通分量，并记录连通分量的大小
for i := 0; i < len(graph); i++ {
for j := 0; j < len(graph[i]); j++ {
if graph[i][j] == 1 {
u.Union(i,j)
}
}
}
// 查找目标，统计每个感染节点的颜色情况
// 先对Init进行排序
sort.Ints(initial)
count := make(map[int]int,0)
for i := 0; i < len(initial); i++ {
count[u.Find(initial[i])]++
}
// 1. 如果有唯一颜色的，就选择其中连通分量最大的
ans := -1
ansSize := -1
root := 0
for i := 0; i < len(initial); i++ {
// 是唯一颜色的
root = u.Find(initial[i])
if count[root] == 1 && (ans == -1 || ansSize < u.Size[root]) {
ans = initial[i]
ansSize = u.Size[root]
}
}
// 2. 如果没有唯一颜色的节点，就选择下标最小的
if ans == -1 {
ans = initial[0]
}
return ans
} |
|
先打个卡 |
思路面试模式35分钟 成功写出bug free代码庆祝 并查集用多了就比较熟悉，这种找连通关系的会很方便，题目本质是求有感染点的连通域，点数最多且感染点只有一个的情况。
代码class Solution:
def minMalwareSpread1(self, graph: List[List[int]], initial: List[int]) -> int:
# 乱写的还出奇的快
uf = {}
n = len(graph)
for i in range(n):
uf[i] = i
def find(x):
t = x
while x != uf[x]:
x = uf[x]
uf[t] = x
return x
for i in range(n):
for j in range(i + 1, n):
if graph[i][j] == 1:
p = find(i)
q = find(j)
if p != q:
uf[q] = p
ans = set()
initial.sort()
for init in initial:
ans.add(find(init))
m = 0
for i in range(n):
if find(i) in ans:
m += 1
m_min = m + 1
for i in range(len(initial)):
ans_r = set()
initial_r = initial[:i] + initial[i + 1:]
for init in initial_r:
ans_r.add(find(init))
m_r = 0
for j in range(n):
if find(j) in ans_r:
m_r += 1
if m_r < m_min:
index = i
m_min = m_r
return initial[index]
def minMalwareSpread2(self, graph: List[List[int]], initial: List[int]) -> int:
# 认真优化越跑越慢
uf = {}
n = len(graph)
for i in range(n):
uf[i] = i
def find(x):
t = x
while x != uf[x]:
x = uf[x]
uf[t] = x
return x
for i in range(n):
for j in range(i + 1, n):
if graph[i][j] == 1:
p = find(i)
q = find(j)
if p != q:
uf[q] = p
num_connected_node = {}
infected_nodes = set(initial)
for i in range(n):
parent = find(i)
if parent not in num_connected_node:
num_connected_node[parent] = [0, 0]
num_connected_node[parent][0] += 1
if i in infected_nodes:
num_connected_node[parent][1] += 1
initial.sort()
num_infected_node = 0
ans = initial[0]
for init in initial:
parent = find(init)
if num_connected_node[parent][1] >= 2:
continue
if num_infected_node < num_connected_node[parent][0]:
num_infected_node = num_connected_node[parent][0]
ans = init
return ans
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
# 套板子写法，最慢但是最稳
uf = UF()
n = len(graph)
for i in range(n):
for j in range(i + 1, n):
if graph[i][j] == 1:
uf.union(i, j)
infected_nodes = collections.defaultdict(int)
for init in initial:
p = uf.find(init)
infected_nodes[p] += 1
initial.sort()
max_node = 0
ans = -1
for init in initial:
p = uf.find(init)
if infected_nodes[p] > 1:
continue
if uf.size[p] > max_node:
max_node = uf.size[p]
ans = init
return initial[0] if ans == -1 else ans
class UF:
def __init__(self):
self.parents = {}
self.size = {}
def find(self, x):
self.parents.setdefault(x, x)
self.size.setdefault(x, 1)
if x != self.parents[x]:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
return x
def union(self, x, y):
p, q = self.find(x), self.find(y)
if p == q:
return
if self.size[p] < self.size[q]:
self.parents[p] = q
self.size[q] += self.size[p]
else:
self.parents[q] = p
self.size[p] += self.size[q] |
|
代码class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int N = graph.length;
DSU dsu = new DSU(N);
for (int i = 0; i < N; ++i)
for (int j = i+1; j < N; ++j)
if (graph[i][j] == 1)
dsu.union(i, j);
int[] count = new int[N];
for (int node: initial)
count[dsu.find(node)]++;
int ans = -1, ansSize = -1;
for (int node: initial) {
int root = dsu.find(node);
if (count[root] == 1) { // unique color
int rootSize = dsu.size(root);
if (rootSize > ansSize) {
ansSize = rootSize;
ans = node;
} else if (rootSize == ansSize && node < ans) {
ansSize = rootSize;
ans = node;
}
}
}
if (ans == -1) {
ans = Integer.MAX_VALUE;
for (int node: initial)
ans = Math.min(ans, node);
}
return ans;
}
}
class DSU {
int[] p, sz;
DSU(int N) {
p = new int[N];
for (int x = 0; x < N; ++x)
p[x] = x;
sz = new int[N];
Arrays.fill(sz, 1);
}
public int find(int x) {
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
public void union(int x, int y) {
int xr = find(x);
int yr = find(y);
p[xr] = yr;
sz[yr] += sz[xr];
}
public int size(int x) {
return sz[find(x)];
}
}复杂度时间复杂度: O(N^2) |
class 尽量减少恶意软件的传播_924_重做版 {
public int minMalwareSpread(int[][] graph, int[] initial) {
int length = graph.length;
UF uf = new UF(length);
for(int i = 0 ; i < length ; i++) {
for(int j = i + 1; j < length; j++) {
if(graph[i][j] == 1) uf.union(i, j);
}
}
Arrays.sort(initial);
int toBeRemove = initial[0];
int curSize = 0;
int[] virusCntUnderRoot = new int[length];
// 每个根节点下有几个病毒 2个或者以上都没法减少 因为删除了自身 自身还是会感染
for(int i : initial) {
virusCntUnderRoot[uf.findRoot(i)] ++;
}
for(int i : initial) {
int root = uf.findRoot(i);
if(virusCntUnderRoot[root] > 1) {
continue;
}
int size = uf.size[root];
if(size>curSize) {
toBeRemove = i;
curSize = size;
}
}
/*for(int i = 0; i< length; i++) {
System.out.println(i + "--->" + uf.root[i] + "--->" + uf.size[i]);
}*/
return toBeRemove;
}
private class UF{
int[] root;
int[] size;
public UF(int c){
root = new int[c];
size = new int[c];
for(int i = 0; i < c; i ++) {
root[i] = i;
size[i] = 1;
}
}
public void union(int p, int q) {
int rootp = findRoot(p);
int rootq = findRoot(q);
if(rootp != rootq) {
root[rootq] = rootp; // 根合并
size[rootp] += size[rootq]; // root下的节点数量累加
}
}
public int findRoot(int p) {
if(root[p] == p) return p;
return root[p] = findRoot(root[p]);
}
}
} |
思路
代码class Solution(object):
def minMalwareSpread(self, graph, initial):
"""
:type graph: List[List[int]]
:type initial: List[int]
:rtype: int
"""
n = len(graph)
color = [None] * n
g = {}
for i in range(n):
g[i] = set()
for j in range(n):
if i != j and graph[i][j] == 1:
g[i].add(j)
now_color = 0
for i in range(n):
if color[i] is None:
self.dfs(i, now_color, color, g)
now_color += 1
color_cnt = [0] * now_color
for i in range(n):
color_cnt[color[i]] += 1
color_flag = [0] * now_color
for i in initial:
color_flag[color[i]] += 1
res = None
remove_cnt = None
for i in initial:
if color_flag[color[i]] == 1:
now_remove = color_cnt[color[i]]
else:
now_remove = 0
if res is None or now_remove > remove_cnt or (now_remove == remove_cnt and res > i):
res = i
remove_cnt = now_remove
return res
def dfs(self, now, now_color, color, g):
color[now] = now_color
for next in g[now]:
if color[next] is None:
self.dfs(next, now_color, color, g)复杂度
|
|
思路
代码javascript /*
* @lc app=leetcode.cn id=924 lang=javascript
*
* [924] 尽量减少恶意软件的传播
*/
// @lc code=start
/**
* @param {number[][]} graph
* @param {number[]} initial
* @return {number}
*/
var minMalwareSpread = function(graph, initial) {
const father = Array.from(graph, (v, i) => i);
function find(v) {
if (v === father[v]) {
return v;
}
father[v] = find(father[v]);
return father[v];
}
function union(x, y) {
if (find(x) !== find(y)) {
father[x] = find(y);
}
}
for (let i = 0; i < graph.length; i++) {
for (let j = 0; j < graph[0].length; j++) {
if (graph[i][j]) {
union(i, j);
}
}
}
initial.sort((a, b) => a - b);
let counts = graph.reduce((acc, cur, index) => {
let root = find(index);
if (!acc[root]) {
acc[root] = 0;
}
acc[root]++;
return acc;
}, {});
let res = initial[0];
let count = -Infinity;
initial
.map((v) => find(v))
.forEach((item, index, arr) => {
if (arr.indexOf(item) === arr.lastIndexOf(item)) {
if (count === -Infinity || counts[item] > count) {
res = initial[index];
count = counts[item];
}
}
});
return res;
};
// @lc code=end复杂度分析
|
|
#define MAX_NUM 301 |
|
IntuitionUse union find Algorithm in python3Complexity Analysis
|
|
class Solution(object): |
type UnionFindSet struct {
Parents []int //记录每个节点的上级
Size []int // 记录以当前结点为顶点的连通分量里面的节点有多少个（只有自己的话，值为1）
}
func (u *UnionFindSet) Init(size int) {
u.Parents = make([]int, size)
u.Size = make([]int, size)
for i := 0; i < size; i++ {
u.Parents[i] = i
u.Size[i] = 1
}
}
func (u *UnionFindSet) Find(node int) int {
if u.Parents[node] == node {
return node
}
root := u.Find(u.Parents[node])
u.Parents[node] = root
return root
}
func (u *UnionFindSet) Union(node1 int, node2 int) {
root1 := u.Find(node1)
root2 := u.Find(node2)
if root1 == root2 {
return
}
if root1 < root2 {
u.Parents[root1] = root2
u.Size[root2] += u.Size[root1] // 以root2为最顶层结点的连通分量的个数要叠加上root1的
}
}
func minMalwareSpread(graph [][]int, initial []int) int {
// 初始化并查集
u := &UnionFindSet{}
u.Init(len(graph))
// 根据graph进行连通，生成连通分量，并记录连通分量的大小
for i := 0; i < len(graph); i++ {
for j := 0; j < len(graph[i]); j++ {
if graph[i][j] == 1 {
u.Union(i,j)
}
}
}
// 查找目标，统计每个感染节点的颜色情况
// 先对Init进行排序
sort.Ints(initial)
count := make(map[int]int,0)
for i := 0; i < len(initial); i++ {
count[u.Find(initial[i])]++
}
// 1. 如果有唯一颜色的，就选择其中连通分量最大的
ans := -1
ansSize := -1
root := 0
for i := 0; i < len(initial); i++ {
// 是唯一颜色的
root = u.Find(initial[i])
if count[root] == 1 && (ans == -1 || ansSize < u.Size[root]) {
ans = initial[i]
ansSize = u.Size[root]
}
}
// 2. 如果没有唯一颜色的节点，就选择下标最小的
if ans == -1 {
ans = initial[0]
}
return ans
} |
class DSU {
private:
vector<int> p, sz;
public:
DSU(int n){
p.resize(n);
for (int i = 0; i < n; ++i){
p[i] = i;
}
sz = vector<int>(n, 1);
}
int Find(int x){
if (p[x] != x){
p[x] = Find(p[x]);
}
return p[x];
}
void Union(int x, int y) {
int xr = Find(x);
int yr = Find(y);
p[xr] = yr;
sz[yr] += sz[xr];
}
int Size(int x) {
return sz[Find(x)];
}
};
class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
DSU dsu(n);
for (int i = 0; i < n; ++i){
for (int j = i + 1; j < n; ++j){
if (graph[i][j] == 1)
dsu.Union(i, j);
}
}
vector<int> count(n);
for (int node : initial){
count[dsu.Find(node)]++;
}
int res = -1, size = -1;
for (int node : initial) {
int root = dsu.Find(node);
if (count[root] == 1) {
int rootSize = dsu.Size(root);
if (rootSize > size) {
size = rootSize;
res = node;
}
else if (rootSize == size && node < res) {
size = rootSize;
res = node;
}
}
}
if (res == -1) {
res = INT_MAX;
for (int node : initial){
res = min(res, node);
}
}
return res;
}
}; |
|
title: "Day 77 924. 尽量减少恶意软件的传播" 924. 尽量减少恶意软件的传播题目在节点网络中，只有当 graph[i][j] = 1 时，每个节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
如果从初始列表中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。
请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后可能仍然因恶意软件传播而受到感染。
示例 1：
输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0
示例 2：
输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
输出：0
示例 3：
输入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
输出：1
提示：
1 < graph.length = graph[0].length <= 300
0 <= graph[i][j] == graph[j][i] <= 1
graph[i][i] == 1
1 <= initial.length < graph.length
0 <= initial[i] < graph.length题目思路
class UnionFind {
public:
vector<int> data;
vector<int> cnt; // 每个节点连通块大小
void init(int n) {
data.resize(n, 0);
for(int i = 0; i < n; i++) {
data[i] = i;
}
cnt.resize(n, 1);
}
int find(int x) {
/* int root = x;
while (data[root] >= 0) root = data[root];
//路径压缩
while (x != root) {
int tmp = data[x]; //tmp 指向 x 的父节点
data[x] = root; //挂到根节点下
x = tmp;
}
return root; //返回根节点的编号。 */
//上述的优化会超时！
if(data[x] != x) {
return find(data[x]);
} else {
return x;
}
}
void Union(int x, int y) {
int p = find(x);
int q = find(y);
data[p] = q;
if (p != q) {
cnt[q] += cnt[p];
}
}
int GetCnt(int x) {
return cnt[find(x)];
}
};
class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
UnionFind u;
int n = graph.size(), m = graph[0].size();
u.init(n);
sort(initial.begin(), initial.end());
for(int i = 0; i < n; i++) {
for (int j = i + 1; j < m; j++) {
if (graph[i][j] == 1) u.Union(i, j);
}
}
// 计算initial中共连通块元素个数
map<int, int> count;
for (auto c : initial) {
count[u.find(c)]++;
}
int ans = -1;
int res = -1;
for (auto c : initial) {
if (count[u.find(c)] == 1) {
int size = u.GetCnt(c);
if (size > res) {
res = size;
ans = c;
}
}
}
if (ans == -1) return initial[0];
return ans;
}
};复杂度
|
JAVA版本思路：使用前缀树的方式（还是不是很懂，先打卡了吧。。。。）
时间复杂度：O(n*n) 空间复杂度：O(n) |
思路并查集，获得每个节点所在集合的个数
class Solution {
Map<Integer,Integer> parents = new HashMap<>();
public int minMalwareSpread(int[][] graph, int[] initial) {
for(int i=0;i<graph.length;i++){
parents.put(i,i);
}
for(int i=0;i<graph.length;i++){
for(int j=0;j<graph.length;j++){
if(graph[i][j] == 1){
union(i,j);
}
}
}
Map<Integer,Integer> rootMap = new HashMap<>();
for(int i=0;i<graph.length;i++){
int root = find(i);
rootMap.put(root,rootMap.getOrDefault(root,0) + 1);
}
Arrays.sort(initial);
Map<Integer,Integer> initRootMap = new HashMap<>();
for(int idx : initial){
int root = find(idx);
if(initRootMap.containsKey(root)){
initRootMap.put(root,0);
} else {
initRootMap.put(root,rootMap.get(root));
}
}
int ans = -1,ansNum = -1;
for(int idx : initial){
int root = find(idx);
int count = initRootMap.get(root);
if(count > ansNum){
ansNum = count;
ans = idx;
}
}
return ans;
}
int find(int idx){
if(parents.get(idx) ==idx)return idx;
int root = find(parents.get(idx));
parents.put(idx,root);
return root;
}
void union(int x , int y){
int xp = find(x);
int yp = find(y);
if(xp == yp)return;
parents.put(xp,yp);
parents.put(x,yp);
}
} |
题目https://leetcode-cn.com/problems/minimize-malware-spread/ 思路unionFind python3class union_find:
def __init__(self):
self.parent = {}
self.size = {}
def find(self, x):
root = x
while(self.parent[root] != root):
root = self.parent[root]
while(x != root):
original_parent = self.parent[x]
self.parent[x] = root
x = original_parent
return root
def merge(self, x, y):
root_x, root_y = self.find(x), self.find(y)
if root_x != root_y:
self.parent[root_x] = root_y
self.size[root_y] += self.size[root_x]
def add(self, x):
if x not in self.parent:
self.parent[x] = x
self.size[x] = 1
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
# time
# space
uf = union_find()
n = len(graph)
for i in range(n):
uf.add(i)
for j in range(i):
if graph[i][j]:
uf.merge(i, j)
print(uf.parent)
print(uf.size)
initial.sort()
max_size, index, fi = 0, -1, []
# using fi store father
# using cnt count the frequency of father
cnt = collections.defaultdict(int)
for init in initial:
fi.append(uf.find(init))
cnt[fi[-1]] += 1
for i in range(len(initial)):
# eg: self.parent = {0:0 1:0}
# cnt[0] = 2
if cnt[fi[i]] > 1:
continue
# using uf.size[father] to compare with max_size
if uf.size[fi[i]] > max_size:
max_size = uf.size[fi[i]]
index = initial[i]
return index if index != -1 else initial[0]复杂度分析
相关题目 |
|
class Solution { } |
思路
class Solution {
vector<int> Father, sz, pc; // pc(point count): 连通块中一共有多少个被感染的点。
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial)
{
const int n = graph.size();
for (int i=0; i < n; i++)
{
Father.push_back(i);
sz.push_back(1);
pc.push_back(0); // 一开始每个连通块都没有被感染的点
}
for(int i=0; i < n; i++)
{
for(int j=0; j < n; j++)
{
if(graph[i][j]==1&&find(i)!=find(j))
{
sz[find(i)] += sz[find(j)];
Father[find(j)] = find(i);
}
}
}
for(auto& x:initial)
pc[find(x)]++;
int rs = -1, rp = INT_MAX;
for (auto& x: initial)
{
if (rs == -1)
rp = min(rp, x); //任意选择一个点，如果没选择过别的点的话。
if(pc[find(x)] == 1) // 当前连通块只包含1个被感染的点的话
{
if(rs < sz[find(x)]) // rs 不如当前的点好的话
{
rs = sz[find(x)];
rp = x;
}
else if (rs == sz[find(x)])
{
rp = min(rp, x); //取编号最小的一个点
}
}
}
return rp;
}
int find(int x)
{
if(Father[x]!=x)
Father[x] = find(Father[x]);
return Father[x];
}
};Complexity:Space:O(n) |
class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int N = graph.length;
DSU dsu = new DSU(N);
for (int i = 0; i < N; ++i)
for (int j = i+1; j < N; ++j)
if (graph[i][j] == 1)
dsu.union(i, j);
int[] count = new int[N];
for (int node: initial)
count[dsu.find(node)]++;
int ans = -1, ansSize = -1;
for (int node: initial) {
int root = dsu.find(node);
if (count[root] == 1) { // unique color
int rootSize = dsu.size(root);
if (rootSize > ansSize) {
ansSize = rootSize;
ans = node;
} else if (rootSize == ansSize && node < ans) {
ansSize = rootSize;
ans = node;
}
}
}
if (ans == -1) {
ans = Integer.MAX_VALUE;
for (int node: initial)
ans = Math.min(ans, node);
}
return ans;
}
}
class DSU {
int[] p, sz;
DSU(int N) {
p = new int[N];
for (int x = 0; x < N; ++x)
p[x] = x;
sz = new int[N];
Arrays.fill(sz, 1);
}
public int find(int x) {
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
public void union(int x, int y) {
int xr = find(x);
int yr = find(y);
p[xr] = yr;
sz[yr] += sz[xr];
}
public int size(int x) {
return sz[find(x)];
}
} |
|
class Solution { } |
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
def find(x):
if x != parents[x]:
parents[x] = find(parents[x])
return parents[x]
def union(x, y):
parents[find(x)] = find(y)
n = len(graph)
parents = [i for i in range(n)]
for i in range(n):
for j in range(i + 1, n):
if graph[i][j] == 1:
union(i, j)
area = collections.Counter(find(i) for i in range(n))
malware = collections.Counter(find(i) for i in initial)
max_size, res = 0, min(initial)
for i in initial:
if malware[find(i)] == 1:
if area[find(i)] > max_size:
max_size, res = area[find(i)], i
elif area[find(i)] == max_size:
res = min(res, i)
return res |
代码class Solution(object):
def minMalwareSpread(self, graph, initial):
# 1. Color each component.
# colors[node] = the color of this node.
N = len(graph)
colors = {}
c = 0
def dfs(node, color):
colors[node] = color
for nei, adj in enumerate(graph[node]):
if adj and nei not in colors:
dfs(nei, color)
for node in xrange(N):
if node not in colors:
dfs(node, c)
c += 1
# 2. Size of each color.
# size[color] = number of occurrences of this color.
size = collections.Counter(colors.values())
# 3. Find unique colors.
color_count = collections.Counter()
for node in initial:
color_count[colors[node]] += 1
# 4. Answer
ans = float('inf')
for x in initial:
c = colors[x]
if color_count[c] == 1:
if ans == float('inf'):
ans = x
elif size[c] > size[colors[ans]]:
ans = x
elif size[c] == size[colors[ans]] and x < ans:
ans = x
return ans if ans < float('inf') else min(initial) |
【Day 77】924. 尽量减少恶意软件的传播代码class Solution {
class DSU {
vector<int> root;
public:
vector<int> size;
vector<int> affected;
DSU(int n) {
size = vector<int>(n, 1);
root.resize(n);
for (int i = 0; i < n; i++)
root[i] = i;
affected.resize(n);
}
int Find(int x) {
if (root[x] != x)
root[x] = Find(root[x]);
return root[x];
}
void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
root[rootX] = rootY;
size[rootY]+= size[rootX];
}
}
};
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
DSU dsu(n * n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (graph[i][j])
dsu.Union(i, j);
}
}
sort(initial.begin(), initial.end());
for (auto i : initial) {
int root = dsu.Find(i);
dsu.affected[root]++;
}
int res = -1;
int num = 0;
for (auto i : initial) {
int root = dsu.Find(i);
if (dsu.affected[root] == 1) {
if (num < dsu.size[root]) {
num = dsu.size[root];
res = i;
}
}
}
return res == -1 ? initial[0] : res;
}
};复杂度时间复杂度：O(N^2) 空间复杂度：O(N) |
|
class Solution { } |
class Solution {
// Logic:
/*
1. union find
2. find the largest union with only one initial node infected by malware
if no such union with only one initial node infected by malware can be found,
return the first initial value
*/
public int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
UF unionFind = new UF(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] == 1) {
unionFind.union(i, j);
}
}
}
Arrays.sort(initial);
// track how many init malware nodes are in each union head
int[] malCount = new int[n];
for (int init : initial) {
malCount[unionFind.find(init)]++;
}
// find the unions with only one initial node infected by malware
// and who is the largest with only one initial
int maxSize = 0;
int potential = -1;
for (int init : initial) {
int head = unionFind.find(init);
if (malCount[head] == 1 && unionFind.size[head] > maxSize) {
maxSize = unionFind.size[head];
potential = init;
}
}
return potential == -1 ? initial[0] : potential;
}
class UF {
int size[];
int parent[];
int numOfUnions;
UF(int numOfElements) {
size = new int[numOfElements];
parent = new int[numOfElements];
numOfUnions = numOfElements;
for (int i = 0; i < numOfElements; i++) {
size[i] = 1;
parent[i] = i;
}
}
int find(int p) {
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
void union(int p, int q) {
int headOfP = find(p);
int headOfQ = find(q);
if (headOfP == headOfQ) {
return;
}
if (size[headOfP] < size[headOfQ]) {
parent[headOfP] = headOfQ;
size[headOfQ] += size[headOfP];
} else {
parent[headOfQ] = headOfP;
size[headOfP] += size[headOfQ];
}
numOfUnions--;
}
}
} |
思路并查集 代码class UnionSet:
def __init__(self,n):
self.parent=[0]*n
self.size=[0]*n
for i in range(n):
self.parent[i]=i
self.size[i]=1
def find(self,x):
if self.parent[x]!=x:
return self.find(self.parent[x])
return x
def merge(self,x,y):
x=self.find(x)
y=self.find(y)
if x!=y:
if self.size[x]<self.size[y]:
x,y=y,x
self.parent[y]=x
self.size[x]+=self.size[y]
def getsize(self,x):
return self.size[self.find(x)]
class Solution:
def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
n=len(graph)
us=UnionSet(n)
for i in range(n):
for j in range(i+1,n):
if graph[i][j]==1:
us.merge(i,j)
cnt=[0]*n
for i in initial:
cnt[us.find(i)]+=1
res=float("inf")
ressize=-1
for i in initial:
p=us.find(i)
if cnt[p]==1:
sz=us.getsize(p)
if sz>ressize or (sz==ressize and p<res):
res=i
ressize=sz
if res==float("inf"):
return min(initial)
return res
|
class Solution {
public int minMalwareSpread(int[][] graph, int[] initial) {
int n = graph.length;
Arrays.sort(initial);
UF uf = new UF(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] == 1) {
uf.union(i, j);
}
}
}
int[] countMap = new int[n]; // each parent to final infected nodes count
for (int i = 0; i < n; i++) {
countMap[uf.find(i)]++;
}
Map<Integer, List<Integer>> infectedMap = new HashMap(); //each parent to its init infection nodes
for (int i : initial) {
infectedMap.computeIfAbsent(uf.find(i), x -> new ArrayList()).add(i);
}
int res = -1;
int maxSize = 0;
for (int x : infectedMap.keySet()) {
if (infectedMap.get(x).size() == 1) {
if (maxSize < countMap[uf.find(x)]) {
maxSize = countMap[uf.find(x)];
res = infectedMap.get(x).get(0);
} else if (maxSize == countMap[uf.find(x)]) {
res = Math.min(res, infectedMap.get(x).get(0));
}
}
}
return res == -1 ? initial[0] : res;
}
private static class UF {
int[] parent;
public UF(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int pX = find(x);
int pY = find(y);
if (pX != pY) {
parent[y] = x;
}
}
}
} |
Solutiondef minMalwareSpread(self, graph, initial):
def find(x):
if x != parents[x]:
parents[x] = find(parents[x])
return parents[x]
def union(x, y):
parents[find(x)] = find(y)
# init
n = len(graph)
parents = range(n)
# union
for i in range(n):
for j in range(i + 1, n):
if graph[i][j] == 1:
union(i, j)
area = collections.Counter(find(i) for i in range(n))
malware = collections.Counter(find(i) for i in initial)
return min(initial, key=lambda i: [(malware[find(i)] == 1) * -area[find(i)], i])Time complexity: O(N^2) |
Intuition
Implementationclass Solution
{
class DisjointSet
{
private:
std::vector<int> id;
std::vector<int> sz;
public:
DisjointSet(int n)
{
id.resize(n);
sz.resize(n);
std::iota(id.begin(), id.end(), 0);
std::fill(sz.begin(), sz.end(), 1);
}
void unite(int x, int y)
{
int xId = find(x);
int yId = find(y);
if (xId == yId) return;
if (sz[xId] < sz[yId]) {
id[xId] = id[yId];
sz[yId] += sz[xId];
} else {
id[yId] = id[xId];
sz[xId] += sz[yId];
}
return;
}
int find(int x)
{
if (x != id[x]) {
id[x] = find(id[x]);
}
return id[x];
}
int getSetSize(int x) { return sz[find(x)]; }
};
public:
int minMalwareSpread(vector<vector<int>> &graph, vector<int> &initial)
{
// build the uptree
int n = graph.size();
DisjointSet ds(n);
for (int jj = 0; jj < n; jj++) {
for (int ii = jj + 1; ii < n; ii++) {
if (graph[jj][ii] == 1) {
ds.unite(jj, ii);
}
}
}
// those initial computers belong to the same set can't be the answer, create a black list for them
std::unordered_map<int, int> blacklist;
for (auto const &ii : initial) {
blacklist[ds.find(ii)]++;
}
int res = *std::min_element(initial.begin(), initial.end());
int maxAffected = -1;
for (auto const &ii : initial) {
if (blacklist[ds.find(ii)] > 1) continue;
int iiSize = ds.getSetSize(ii);
if (iiSize > maxAffected) {
res = ii;
maxAffected = iiSize;
} else if (iiSize == maxAffected && ii < res) {
res = ii;
}
}
return res;
}
};Complexity
|
class Solution {
public:
vector<int> p, s, c;
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
for (int i = 0; i < n; i++) {
p.push_back(i);
s.push_back(1);
c.push_back(0);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j ++) {
if (graph[i][j] && find(i) != find(j)) {
s[find(i)] += s[find(j)];
p[find(j)] = find(i);
}
}
}
for (auto x: initial) c[find(x)] ++;
int rs = -1, rp = INT_MAX;
for (auto x: initial) {
if (rs == -1) rp = min(rp, x);
if (c[find(x)] == 1) {
if (rs < s[find(x)]) {
rs = s[find(x)];
rp = x;
} else if (rs == s[find(x)]) {
rp = min(rp, x);
}
}
}
return rp;
}
}; |
思路UFS 代码class Solution {
private:
int ufsFind(vector<int>& ufs, int x) {
if (ufs[x] < 0)
return x;
ufs[x] = ufsFind(ufs, ufs[x]);
return ufs[x];
}
int ufsUnion(vector<int>& ufs, int x, int y) {
int rx = ufsFind(ufs, x);
int ry = ufsFind(ufs, y);
if (rx == ry)
return -1;
ufs[rx] += ufs[ry];
ufs[ry] = rx;
return ufs[rx];
}
int ufsSize(vector<int>& ufs, int x) {
int rx = ufsFind(ufs, x);
return -ufs[rx];
}
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int res;
int n = graph.size();
vector<int> ufs(n, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j)
continue;
if (graph[i][j])
ufsUnion(ufs, i, j);
}
}
// sort(initial.begin(), initial.end());
int max = 0;
for (int i = 0; i < initial.size(); ++i) {
int size = ufsSize(ufs, initial[i]);
if (size > max) {
max = size;
res = i;
}
}
return res;
}
}; |
思路并查集 代码class Solution {
private:
int ufsFind(vector<int>& ufs, int x) {
if (ufs[x] < 0)
return x;
ufs[x] = ufsFind(ufs, ufs[x]);
return ufs[x];
}
int ufsUnion(vector<int>& ufs, int x, int y) {
int rx = ufsFind(ufs, x);
int ry = ufsFind(ufs, y);
if (rx == ry)
return -1;
ufs[rx] += ufs[ry];
ufs[ry] = rx;
return ufs[rx];
}
int ufsSize(vector<int>& ufs, int x) {
int rx = ufsFind(ufs, x);
return -ufs[rx];
}
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int res;
int n = graph.size();
vector<int> ufs(n, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j)
continue;
if (graph[i][j])
ufsUnion(ufs, i, j);
}
}
// sort(initial.begin(), initial.end());
int max = 0;
for (int i = 0; i < initial.size(); ++i) {
int size = ufsSize(ufs, initial[i]);
if (size > max) {
max = size;
res = i;
}
}
return res;
}
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and others
924. 尽量减少恶意软件的传播
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/minimize-malware-spread
前置知识
暂无
题目描述
The text was updated successfully, but these errors were encountered: