记 \(N(u)\) 表示图上与点 \(u\) 相邻的点，\(p_u = deg_u - a_u\)，其中 \(deg_u\) 为无向图上点 \(u\) 的度数。首先要删除 \(p_u = 0\) 的点，同时 \(\forall v \in N(u), p_v \gets p_v - 1\)，归纳地考虑 \(p\) 为 \(0\) 的点即可。由于题目中保证至少存在一个移除序列，所以通过此方式一定可以求得一组合法解。
Additionally: 若给出序列不存在任何合法解，当且仅当在上述算法中，出现了 \(p_u < 0\) 的点或算法结束后仍有未被删除的点。
构造出一组合法解后，考虑该解有何性质。
\(\text{Lemma 1.}\) 对于节点 \(u\)，点集 \(N(u)\) 中有且仅有 \(p_u\) 个先于它被删除的节点，且对于所有的合法移除序列，这 \(p_u\) 个节点是相同的（\(\text{i.e.}\) 这 \(p_u\) 个节点总是先于 \(u\) 被移除）。
\(\text{Proof.}\) 由于节点 \(u\) 可被移除当且仅当 \(p_u = 0\)，显然我们需要 \(p_u\) 个先于 \(u\) 被删除的节点。假设 \(N(u)\) 中存在一个不属于原先 \(p_u\) 个节点中的节点 \(t\)，使得 \(t\) 先于 \(u\) 被移除，这也意味着原先的 \(p_u\) 个节点中出现了一个节点 \(k\) 需要后于 \(u\) 被删除。这样一来，节点 \(k\) 原先需要在点集 \(N(k) \backslash \{ u \}\) 中选 \(p_k\) 个先于 \(k\) 删除的节点，现在只需选择 \(p_k - 1\) 个节点，类似地，剩余那个节点也只需要选择（原先需要的点数 - 1）个节点。这个过程形成了一个归纳，归纳到最后，我们一定会遇到 \(p\) 值为 \(0\) 的节点，这个节点原先需要先于任何与之相邻的节点被删除，然而归纳过程中我们先删除了与其相邻的某个节点，这就导致不合法情况的诞生。因此假设不成立，证毕。
因此，由引理，只需要构造出一组合法解，便可知点对被移除的先后顺序是否固定。我们可以对原图中所有无向边按该解中的先后顺序定向，具体地，对于边 \((u, v)\)，若 \(u\) 在序列中先于 \(v\) 出现，则连接一条 \(u \to v\) 的有向边。这样一来，若两点在新图上连通，则其被删除的先后顺序一定是确定的。这样一来就是一个有向图可达点对计数问题了。记可达点对数为 \(num\)，则答案为 \(\frac{n(n - 1)}{2} - num\)。
记 \(c_u\) 表示 \(u\) 到 \(n\) 个点是否可达的状态（使用 bitset）。容易发现最终得到的图一定是一个 DAG，建反图后进行拓扑排序，按拓扑序先后考虑，对于节点 \(u\)，\(\forall v \in N(u), c_v \gets c_u \text{ or } c_v\) 即可。时间复杂度 \(\mathcal{O} (\frac{n ^ 2}{w})\)，空间复杂度 \(\mathcal{O} (\frac{n ^ 2}{w})\)，大约 \(\text{1192 MB}\)。分段考虑，每次只考虑每个点点到 \(1000\) 个点是否可达的状态，这样便可以优化空间了。（官方题解还有一种更好的做法，以 64 为段长并使用 unsigned long long 代替 bitset，使用 __builtin_popcountll 函数统计，此时 \(w = 64\)，可以大幅降低用时，学到了）
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 1e5 + 10, B = 1000;
int deg[N], a[N], p[N], n, m;
vector<int> G[N], G2[N];
vector<int> res;
queue<int> S;
bitset<B> c[N];
void topo1(){
res.clear();
for(int i = 1; i <= n; i++)
if(p[i] == 0) S.push(i);
while(!S.empty()){
int u = S.front(); S.pop(); res.push_back(u);
for(auto &v : G[u])
if(--p[v] == 0) S.push(v);
}
}
void topo2(){
res.clear();
for(int i = 1; i <= n; i++)
if(deg[i] == 0) S.push(i);
while(!S.empty()){
int u = S.front(); S.pop(); res.push_back(u);
for(auto &v : G2[u])
if(--deg[v] == 0) S.push(v);
}
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i], deg[i] = 0, G[i].clear(), G2[i].clear();
vector<int> u(m), v(m);
for(int i = 0; i < m; i++){
cin >> u[i] >> v[i];
G[u[i]].push_back(v[i]); G[v[i]].push_back(u[i]);
deg[u[i]]++, deg[v[i]]++;
}
for(int i = 1; i <= n; i++)
p[i] = deg[i] - a[i];
topo1();
vector<int> inv(n + 1);
for(int i = 0; i < n; i++)
inv[res[i]] = i;
for(int i = 1; i <= n; i++)
deg[i] = 0;
for(int i = 0; i < m; i++){
if(inv[u[i]] < inv[v[i]])
G2[v[i]].push_back(u[i]), deg[u[i]]++;
else G2[u[i]].push_back(v[i]), deg[v[i]]++;
// 注意 G2 是一个反图
}
topo2();
i64 ans = 1ll * n * (n - 1) / 2;
for(int i = 1; i <= n; i += B){
for(int j = 0; j < n; j++){
int x = res[j];
if(i <= x && x < i + B) c[x][x - i] = 1, ans++;
for(auto &y : G2[x])
c[y] |= c[x];
}
for(int j = 1; j <= n; j++)
ans -= c[j].count(), c[j].reset();
}
cout << ans << "\n";
}