3656. Determine if a Simple Graph Exists
You are given an integer array degrees, where degrees[i] represents the desired degree of the ith vertex.
Your task is to determine if there exists an undirected simple graph with exactly these vertex degrees.
A simple graph has no self-loops or parallel edges between the same pair of vertices.
Return true if such a graph exists, otherwise return false.
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
| class Solution {
public:
bool simpleGraphExists(vector<int>& A) {
if(A.size() == 0) return true;
sort(rbegin(A), rend(A));
vector<long long> pre{0};
for(auto& n : A) pre.push_back(pre.back() + n);
if(pre.back() & 1) return false;
for(long long i = 1; i < pre.size(); i++) {
long long le = pre[i], ri = i * (i - 1);
long long l = i, r = pre.size() - 2, best = -1;
while(l <= r) {
long long m = l + (r - l) / 2;
if(A[m] <= i) {
best = m;
r = m - 1;
} else l = m + 1;
}
if(best == -1) ri += (A.size() - i) * i;
else ri += (best - i) * i + pre.back() - pre[best];
if(le > ri) return false;
}
return true;
}
};
|
