Re: [閒聊] 每日leetcode
2493. Divide Nodes Into the Maximum Number of Groups
## 思路
每個點做BFS
如果不是bipartite 就回傳-1
把遇到的最小點當作GROUP ID 更新GROUP的長度
最後再把每個GROUP的長度加總
## Code
```cpp
class Solution {
public:
int magnificentSets(int n, vector<vector<int>>& edges) {
vector<vector<int>> adjList(n);
for (auto& edge: edges) {
adjList[edge[0]-1].push_back(edge[1]-1);
adjList[edge[1]-1].push_back(edge[0]-1);
}
unordered_map<int, int> distance;
for (int i=0; i<n; ++i) {
queue<int> q({i});
vector<int> group(n, -1);
group[i] = 0;
int level = 0;
int minNode = i;
while(!q.empty()) {
int count = q.size();
while (count--) {
int curr = q.front();
q.pop();
minNode = min(minNode, curr);
for (int neighbor: adjList[curr]) {
if (group[neighbor] == -1) {
group[neighbor] = group[curr] ^ 1;
q.push(neighbor);
} else if (group[neighbor] != (group[curr] ^ 1)) {
return -1;
}
}
}
level++;
}
if (distance.contains(minNode)) {
distance[minNode] = max(distance[minNode], level);
} else {
distance[minNode] = level;
}
}
int res = 0;
for (const auto& [key, value] : distance) {
res += value;
}
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 87.120.102.91 (義大利)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1738206330.A.20A.html
討論串 (同標題文章)
完整討論串 (本文為第 1315 之 1553 篇)：