题目来源:https://leetcode.com/problems/regions-cut-by-slashes/description/

标记难度:Medium

提交次数:2/5

代码效率:

  • 并查集:12ms
  • DFS:28ms

题意

用字符画的形式给定一个N*N的格子里的分割线,如:

1
2
\/
/\

问图中共有多少个连通区域。

分析

比赛的时候我就想到了把每个格子分成四个三角形的方法。但是我当时尝试在类里开一个3600*3600的静态数组,所以RE了。不过它只会RE而不会报MLE,这令人很难调试……反正直接用邻接矩阵肯定是不行的。


一种方法是直接绕开邻接矩阵和邻接表,用并查集来解决。

另一种看起来很神奇的方法[1]是,直接用upscale的思路把每个格子分成9块,然后令线的方格为障碍物,其他方格为可通过,这样也可以做DFS(或者说floodfill)。事实上这种建模的思路是隐式地建了每个小方格和周围的4个方格之间的图。

最后,当然用邻接表+DFS也可以啦。

代码

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
private:
int _fa[3600];
int N, M;
void init() {
for (int i = 0; i < M; i++)
_fa[i] = i;
}

int fa(int x) {
return x == _fa[x] ? x : _fa[x] = fa(_fa[x]);
}

void merge(int x, int y) {
x = fa(x);
y = fa(y);
_fa[x] = y;
}

public:
int regionsBySlashes(vector<string>& grid) {
// 4N^2 small triangles
N = grid.size();
M = 4*N*N;
init();
// initial merge
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
int n = 4*(i*N + j);
if (i < N - 1) {
int n1 = 4*((i+1)*N + j);
merge(n+2, n1);
}
if (j < N - 1) {
int n1 = 4*(i*N + j+1);
merge(n+1, n1+3);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int n = 4*(i*N + j);
if (grid[i][j] != '/') {
merge(n, n+1);
merge(n+2, n+3);
}
if (grid[i][j] != '\\') {
merge(n, n+3);
merge(n+1, n+2);
}
}
}
int ans = 0;
for (int i = 0; i < M; i++) {
if (fa(i) == i)
ans++;
}
return ans;
}
};

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
private:
int N;
vector<int> G[3600];
void connect(int x, int y) {
G[x].push_back(y);
G[y].push_back(x);
}
bool visited[3600];

void dfs(int x) {
for (auto const& y: G[x])
if (!visited[y]) {
visited[y] = true;
dfs(y);
}
}

public:
int regionsBySlashes(vector<string>& grid) {
N = grid.size();
// initial links
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
int n = 4*(i*N + j);
if (i < N - 1) {
int n1 = 4*((i+1)*N + j);
connect(n+1, n1+3);
}
if (j < N - 1) {
int n1 = 4*(i*N + j+1);
connect(n+2, n1);
}
}
// grid picture
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int n = 4*(i*N + j);
if (grid[i][j] != '\\') {
connect(n, n+3);
connect(n+1, n+2);
}
if (grid[i][j] != '/') {
connect(n, n+1);
connect(n+2, n+3);
}
}
}

int ans = 0;
memset(visited, 0, sizeof(visited));
for (int i = 0; i < 4*N*N; i++) {
if (!visited[i]) {
visited[i] = true;
ans++;
dfs(i);
}
}
return ans;
}
};

  1. vortrubac's Solution for Leetcode 959 - C++ with picture, DFS on upscaled grid

题目来源:https://leetcode.com/problems/largest-component-size-by-common-factor/description/

标记难度:Hard

提交次数:7/8

代码效率:

  • 埃式筛法,map存储分解结果,普通并查集:1324ms
  • 埃式筛法,map存储分解结果,size优化并查集:1452, 1848ms
  • 欧拉筛法,map存储分解结果,普通并查集:TLE, 1868ms
  • 埃式筛法(减少素数),map存储分解结果,普通并查集:144ms
  • 素数打表,map存储分解结果,普通并查集:132ms
  • 素数打表,手写链表,普通并查集:132ms

题意

给定一些结点,每个结点上有一个值,令两个结点有边相连当且仅当上面的值有大于1的公因子。问图中最大的连通分量的大小。

结点数量在[1, 20000]范围内,值的大小在[1, 100000]范围内。

分析

这道题有一个显然的做法:

  • 首先打一个质数表。
    • 我之前认为需要打[1, 100000]范围内的质数(事实证明,一共有九千多个),但事实上不需要,只要打[1, sqrt(100000)]范围内的素数就可以了。在做质因数分解的时候,如果用上述范围内的质数没能约到1,则剩下的数必然是个大素数,不需要打表打到这个范围。
    • 打表可以用埃式筛法或者欧拉筛法(我之前在某次模拟赛中做过类似的题)。
  • 然后对每个数值作质因数分解,对每个质数开一个链表(或者类似的结构),如果一个质数是某个数的因数,就把这个数(的index)放到链表中。
  • 然后对每条链表中的值在并查集中作合并操作。
  • 最后找出并查集中最大的集合。

然后可以进行一些优化:

  • 换成欧拉筛法(结果耗时反而变多了)
  • 对并查集进行size优化(结果耗时反而变多了)
  • 只打sqrt(100000)范围内的质数表(耗时骤降,变成约10%)
  • 手工打质数表(耗时稍微减少)
  • map换成手写链表(耗时居然没变)

想到算法的复杂度实际上是O(NP),少遍历质数表好像的确能降低复杂度……

以及我在评论区里看到一个直接在做欧拉筛的时候进行合并的方法[1],非常简洁(但好像没有我快?看来打整张质数表还是太耗费时间了)。

代码

这次提交了很多版本的代码,这里放两个最快的好了。

map版本

132ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
private:
// 并查集
int _fa[20005];
int _size[20005];
int n;

void init() {
for (int i = 0; i < n; i++) {
_fa[i] = i;
_size[i] = 1;
}
}

int fa(int x) {
if (_fa[x] == x) return x;
_size[_fa[x]] += _size[x];
_size[x] = 0;
return _fa[x] = fa(_fa[x]);
}

int merge(int x, int y) {
x = fa(x);
y = fa(y);
if (_size[x] < _size[y]) swap(x, y);
_fa[y] = x;
return fa(y);
}

int size(int x) {
x = fa(x);
return _size[x];
}

public:
int largestComponentSize(vector<int>& A) {
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
269, 271, 277, 281, 283, 293, 307, 311, 313, 317};
int m = sizeof(primes) / sizeof(int);
// 质因数分解,插入对应的vector
map<int, vector<int>> primeMap;
n = A.size();
for (int i = 0; i < n; i++) {
int x = A[i];
int j = 0;
while (j < m) {
if (x == 1) break;
while (j < m && x % primes[j] != 0) j++;
if (j >= m) break;
while (x % primes[j] == 0) x /= primes[j];
primeMap[primes[j]].push_back(i);
j++;
}
if (x != 1) primeMap[x].push_back(i);
}
// 合并每个质因数对应的所有数
init();
for (auto const& p: primeMap) {
if (p.second.size() > 1) {
int fa0 = fa(p.second[0]);
for (int i = 1; i < p.second.size(); i++) {
fa0 = merge(fa0, p.second[i]);
}
}
}
// 找到最大的集合,输出结果
int maxn = -1;
for (int i = 0; i < n; i++)
maxn = max(maxn, size(i));
return maxn;
}
};

链表版本

也是132ms。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class Solution {
private:
// 并查集
int _fa[20005];
int _size[20005];
int n;

void init() {
for (int i = 0; i < n; i++) {
_fa[i] = i;
_size[i] = 1;
}
}

int fa(int x) {
if (_fa[x] == x) return x;
_size[_fa[x]] += _size[x];
_size[x] = 0;
return _fa[x] = fa(_fa[x]);
}

int merge(int x, int y) {
x = fa(x);
y = fa(y);
if (_size[x] < _size[y]) swap(x, y);
_fa[y] = x;
return fa(y);
}

int size(int x) {
x = fa(x);
return _size[x];
}

// 链表
struct Node {
int val;
Node* next;

Node(int x) {
val = x;
next = NULL;
}
};

Node* heads[100000];
inline void insert(int prime, int i) {
Node* node = new Node(i);
node->next = heads[prime];
heads[prime] = node;
}

public:
int largestComponentSize(vector<int>& A) {
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263,
269, 271, 277, 281, 283, 293, 307, 311, 313, 317};
int m = sizeof(primes) / sizeof(int);
// 质因数分解,插入对应链表
n = A.size();
memset(heads, 0, sizeof(heads));
for (int i = 0; i < n; i++) {
int x = A[i];
int j = 0;
while (j < m) {
if (x == 1) break;
while (j < m && x % primes[j] != 0) j++;
if (j >= m) break;
while (x % primes[j] == 0) x /= primes[j];
insert(primes[j], i);
j++;
}
if (x != 1) insert(x, i);
}
// 合并每个质因数对应的所有数
init();
for (int i = 2; i < 100000; i++) {
if (heads[i] != NULL) {
int fa0 = fa(heads[i]->val);
Node* p = heads[i]->next;
for (p != NULL; p != NULL; p = p->next) {
fa0 = merge(fa0, p->val);
}
}
}
// 找到最大的集合,输出结果
int maxn = -1;
for (int i = 0; i < n; i++)
maxn = max(maxn, size(i));
return maxn;
}
};

  1. groawr's Solution for Leetcode 952 - C++ Sieve of Erastosthenes

题目来源:https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/description/

标记难度:Medium

提交次数:1/1

代码效率:40ms

题意

给定一个2D平面和一些位于自然数坐标上的小石子(坐标不会重复);如果某个石子和其他石子位于同一行同一列上,则可以把它移除;问最多能移走多少个小石子。

分析

比赛的时候我想了很久也没想出来……(然后就去吃饭了)。我的确想到了把在同一行同一列上的石子都连起来然后找连通子图数量这种做法,但我竟然觉得它有反例……(现在我已经知道我当初是怎么想错的了)


第一个问题是怎么证明一个大的连通子图一定能reduce成一颗石子。我感觉这并不是一件显然的事情。

(嗯,确实没有那么显然……)

一种方法是,构造一颗这个子树的生成树。(从一个无向连通图能够生成一颗生成树这件事应该够显然的了)然后不断移除这棵树的叶子结点,直到最后只剩下根结点。[1]

当然,事实上不需要真的把这些都构造出来,只要知道就可以了。

然后我感觉直接DFS就可以了……并查集当然也可以。

代码

懒得写并查集了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
private:
int n;
vector<pair<int, int>> stoneCoors;
map<int, vector<int>> rows, cols;
set<int> rowsVisited, colsVisited;

void dfs(int x, int r, int c) {
// cout << x <<' ' << r << ' ' << c << endl;
if (rowsVisited.find(r) == rowsVisited.end()) {
rowsVisited.insert(r);
for (int y: rows[r])
if (y != x && colsVisited.find(stoneCoors[y].second) == colsVisited.end())
dfs(y, stoneCoors[y].first, stoneCoors[y].second);
}
if (colsVisited.find(c) == colsVisited.end()) {
colsVisited.insert(c);
for (int y: cols[c])
if (y != x && rowsVisited.find(stoneCoors[y].first) == rowsVisited.end())
dfs(y, stoneCoors[y].first, stoneCoors[y].second);
}
}

public:
int removeStones(vector<vector<int>>& stones) {
n = stones.size();
for (int i = 0; i < n; i++) {
stoneCoors.emplace_back(stones[i][0], stones[i][1]);
}
sort(stoneCoors.begin(), stoneCoors.end());
for (int i = 0; i < n; i++) {
rows[stoneCoors[i].first].push_back(i);
cols[stoneCoors[i].second].push_back(i);
}

int ans = 0;
for (int i = 0; i < n; i++) {
if (rowsVisited.find(stoneCoors[i].first) == rowsVisited.end() ||
colsVisited.find(stoneCoors[i].second) == colsVisited.end()) {
// cout << i << endl;
ans++;
dfs(i, stoneCoors[i].first, stoneCoors[i].second);
}
}

return n - ans;
}
};

  1. Leetcode Official Solution for 947. Most Stones Removed with Same Row or Column

题目来源:https://leetcode.com/problems/minimize-malware-spread-ii/description/

标记难度:Hard

提交次数:2/2

代码效率:

  • 暴力DFS:104ms
  • 优化过的DFS:108ms
  • 优化过的并查集:懒得写了

题意

有一个无向图,图中有些结点被感染了,感染会通过图的边传播。现在可以移除一个初始被感染的结点(是移除,而不是让它不被感染),问移除哪一个结点可以使最终被感染的总结点数最小?如果有多个结点,输出编号最小的一个。

分析

呃,这道题的题意正好和我上次看错的是一样的……于是我当然直接用了最暴力的方法,手动模拟每个初始感染结点被删除之后的感染状况。当然我觉得这种方法看起来还不差,因为DFS的复杂度是O(N),DFSN次的复杂度就是O(N^2);不过显然我这样想的时候没有考虑到题目里给出的图是邻接矩阵表示(而非邻接表),所以实际复杂度应该是O(N^3)。不过反正N <= 300,N^2和N^3也差不多。(……)

优化过的DFS

首先将所有初始感染结点从图里移除;然后对于每个初始感染结点,通过DFS找到它能够感染的结点集合;然后对于每个普通结点,找出它会被多少个结点感染。如果它只能被某一个结点感染,移除该结点就可以使得该普通结点不会被感染。然后找到其中的最大值即可。[1]

我的一个疑惑是,为何是把所有初始感染结点都移除,而不是把所有的结点都留在图里,然后找到某一个结点能感染的结点集合?这两点的区别显然是,把其他的结点留在图里之后,某一个结点能感染的结点集合就会变大,甚至包含一些移除了别的结点之后不能被感染的结点,这大约是不合适的。

另一个问题是,考虑到邻接矩阵的问题,这个方法的时间复杂度是不是仍然是O(N^3)……事实证明运行时间差不多。

优化过的并查集

这个方法的思路和上一个差不多,不过是把DFS换成并查集,然后判断每个分量和多少个初始感染结点相邻。(就是写得更明白一点了。)我感觉这个方法是O(N^2)的(因为相比DFS节省了很多无用的计算),不过我现在不是很想写了。[1]

代码

暴力DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
private:
void dfs(int cur, vector<vector<int>>& graph, int &cnt, const int& removed, bool visited[]) {
for (int y = 0; y < graph[cur].size(); y++) {
if (graph[cur][y] && !visited[y] && y != removed) {
visited[y] = true;
cnt++;
dfs(y, graph, cnt, removed, visited);
}
}
}

public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
// completely remove
sort(initial.begin(), initial.end());
int n = graph.size();
int ans = n + 1, index = -1;
bool visited[n];
for (int x: initial) {
memset(visited, false, sizeof(visited));
int cnt = 0;
for (int y: initial) {
if (x != y && !visited[y]) {
visited[y] = true;
cnt++;
dfs(y, graph, cnt, x, visited);
}
}
if (cnt < ans) {
index = x;
ans = cnt;
}
}
return index;
}
};

优化过的DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
private:
void dfs(int cur, const int& x, vector<vector<int>>& graph, bool isRemoved[], unordered_set<int> affect[]) {
for (int i = 0; i < graph.size(); i++) {
if (graph[cur][i] && !isRemoved[i] && affect[x].find(i) == affect[x].end()) {
affect[x].insert(i);
dfs(i, x, graph, isRemoved, affect);
}
}
}

public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
int n = graph.size();
bool isRemoved[n];
memset(isRemoved, 0, sizeof(isRemoved));
for (int x: initial)
isRemoved[x] = true;

// 分别DFS
unordered_set<int> affect[n];
for (int x: initial) {
isRemoved[x] = false;
affect[x].insert(x);
dfs(x, x, graph, isRemoved, affect);
isRemoved[x] = true;
}

// 每个结点会被哪些结点感染
unordered_set<int> affectedBy[n];
for (int i = 0; i < n; i++) {
for (int x: affect[i])
affectedBy[x].insert(i);
}

// 只被一个结点感染的结点
int singleCnt[n];
memset(singleCnt, 0, sizeof(singleCnt));
for (int i = 0; i < n; i++) {
if (!isRemoved[i] && affectedBy[i].size() == 1)
singleCnt[*affectedBy[i].begin()]++;
}

// 取最大值
int index = -1, maximum = -1;
for (int i = 0; i < n; i++) {
if (isRemoved[i] && singleCnt[i] > maximum) {
index = i;
maximum = singleCnt[i];
}
}

return index;
}
};

  1. Leetcode Official Solution for 928. Minimize Malware Spread II

题目来源:https://leetcode.com/problems/minimize-malware-spread/description/

标记难度:Hard

提交次数:3/7

代码效率:

  • 暴力:256ms
  • DFS:216ms
  • 并查集:108ms

题意

有一个无向图,图中有些结点被感染了,感染会通过图的边传播。现在可以移除一个初始被感染的结点,问移除哪一个结点可以使最终被感染的总结点数最小?如果有多个结点,输出编号最小的一个。

分析

我比赛的时候居然交了4次……

  • 第一次写了一个巨暴力的方法:每次移除一个初始感染结点,然后用DFS计算被感染结点总数。然后我还没写对。题目表明“使一个结点初始不被感染,它仍然有可能被传播到感染”,所以直接把结点从图里去掉是不可取的。而且很不幸的是,我还把graph当成邻接表了(事实上应该是邻接矩阵)。
  • 第二次我尝试调这个暴力,但是我对题意产生了一点误解:如果有多个合法结点,是输出在vector<int> initial中index最小的结点,还是输出编号最小的结点?事实证明应该是编号最小的结点,但我这一次改成了index最小,那自然是没有什么对的可能了。
  • 第三次我还在调这个暴力,但并没有发现核心问题。
  • 第四次我仍然在调这个暴力,此时发现了graph的问题,但还是对题目内容有着非常深刻的误解。(而且此时已经10:55了。)

其实交第一次之前我是想到了正解的(无论是用DFS,还是并查集),但紧接着我就由于各种原因把题给看错了……这可真是太不可取了。


上面说的暴力算法的复杂度应该是O(M * N + M)M = initial.lengthN = graph.length)。原来这样就能过了吗……不愧是1 <= graph.length <= 300

DFS

这个思路很容易想到。用DFS对图中的连通分量(如果我没有搞错图论术语的话)进行染色,这样就可以知道每个结点对应的连通分量和连通分量的大小了;然后统计每个连通分量中所包含的初始感染结点的数量,如果该连通分量只包含一个初始感染结点,则移除该感染结点可以防止整个连通分量的结点受到感染;否则移除该结点不会改变受感染结点的总数。然后取最小值即可。

DFS的时间复杂度是O(N),统计结点数量的复杂度是O(M),总复杂度为O(N + M)

并查集

这个思路和DFS基本类似,只是换成用并查集来进行着色而已。[1]

代码

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
private:
int n;

void dfs(int x, vector<vector<int>>& graph, int& cnt, bool visited[]) {
for (int i = 0; i < n; i++) {
if (graph[x][i] && !visited[i]) {
cnt++;
visited[i] = true;
dfs(i, graph, cnt, visited);
}
}
}

public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
n = graph.size();
bool visited[n];
int minimum = n + 1, index = -1;
sort(initial.begin(), initial.end());
for (int i = 0; i < initial.size(); i++) {
memset(visited, 0, sizeof(visited));
// remove i
int cnt = 0;
for (int j = 0; j < initial.size(); j++) {
if (j != i && !visited[initial[j]]) {
visited[initial[j]] = true;
cnt++;
dfs(initial[j], graph, cnt, visited);
}
}
//cout << initial[i] << ' ' << cnt << endl;
if (cnt < minimum) {
minimum = cnt;
index = initial[i];
}
}
return index;
}
};

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
private:
int n;

void dfs(int x, int c, vector<vector<int>>& graph, int color[], int colorNum[]) {
for (int y = 0; y < n; y++)
if (graph[x][y] && !color[y]) {
color[y] = c;
colorNum[c]++;
dfs(y, c, graph, color, colorNum);
}
}

public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
n = graph.size();
// color the graph
int color[n + 1], colorNum[n + 1];
memset(color, 0, sizeof(color));
int c = 1;
for (int i = 0; i < n; i++) {
if (!color[i]) {
color[i] = c;
colorNum[c] = 1;
dfs(i, c, graph, color, colorNum);
c++;
}
}
// find colors of initials
// 此处也可以不排序的,多加一些特判就行了……
sort(initial.begin(), initial.end());
int initialsInColors[n + 1];
memset(initialsInColors, 0, sizeof(initialsInColors));
for (int x: initial) {
initialsInColors[color[x]]++;
}
int maxn = -1, index = -1;
for (int x: initial) {
if (initialsInColors[color[x]] <= 1 && colorNum[color[x]] > maxn) {
maxn = colorNum[color[x]];
index = x;
}
else if (initialsInColors[color[x]] > 1 && 0 > maxn) {
maxn = 0;
index = x;
}
}
return index;
}
};

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
private:
int n;

int fa[305], cnt[305];

void init() {
for (int i = 0; i < n; i++) {
fa[i] = i;
cnt[i] = 1;
}
}

int find(int x) {
if (x == fa[x]) return x;
else {
cnt[fa[x]] += cnt[x];
cnt[x] = 0;
return fa[x] = find(fa[x]);
}
}

int getcnt(int x) {
return cnt[find(x)];
}

void merge(int x, int y) {
x = find(x);
y = find(y);
if (cnt[x] >= cnt[y]) swap(x, y);
fa[x] = y;
find(x);
}

public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
n = graph.size();
init();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (graph[i][j])
merge(i, j);
int facnt[n];
memset(facnt, 0, sizeof(facnt));
for (int x: initial)
facnt[find(x)]++;
int maxn = -1, index = n + 1;
for (int x: initial) {
if (facnt[find(x)] <= 1 && (getcnt(x) > maxn || getcnt(x) == maxn && x < index)) {
maxn = getcnt(x);
index = x;
}
else if (0 > maxn || maxn == 0 && x < index) {
maxn = 0;
index = x;
}
}
return index;
}
};

  1. lee215's Union Found Solution