Removal Sequences (Codeforces 1795G)
Tags: Others, graphs

You are given a simple undirected graph, consisting of $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th vertex has a value $$$a_i$$$ written on it.You will be removing vertices from that graph. You are allowed to remove vertex $$$i$$$ only if its degree is equal to $$$a_i$$$. When a vertex is removed, all edges incident to it are also removed, thus, decreasing the degree of adjacent non-removed vertices.A valid sequence of removals is a permutation $$$p_1, p_2, \dots, p_n$$$ $$$(1 \le p_i \le n)$$$ such that the $$$i$$$-th vertex to be removed is $$$p_i$$$, and every removal is allowed.A pair $$$(x, y)$$$ of vertices is nice if there exist two valid sequences of removals such that $$$x$$$ is removed before $$$y$$$ in one of them and $$$y$$$ is removed before $$$x$$$ in the other one.Count the number of nice pairs $$$(x, y)$$$ such that $$$x < y$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.The first line of each testcase contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$; $$$0 \le m \le \min(10^5, \frac{n \cdot (n - 1)}{2})$$$) — the number of vertices and the number of edges of the graph.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n - 1$$$) — the degree requirements for each removal.Each of the next $$$m$$$ lines contains two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$) — the description of an edge.The graph doesn't contain any self-loops or multiple edges.The sum of $$$n$$$ over all testcases doesn't exceed $$$10^5$$$. The sum of $$$m$$$ over all testcases doesn't exceed $$$10^5$$$.Additional constraint on the input: there always exists at least one valid sequence of removals.

Output: For each testcase, print a single integer — the number of nice pairs of vertices.


Sample Inputs:
4
3 2
1 0 1
2 3
1 2
3 3
1 2 0
1 2
2 3
1 3
5 6
3 0 2 1 0
1 2
4 1
4 2
3 4
2 3
5 1
1 0
0

Sample Outputs:
1
0
4
0

Solution (Python):
import sys
from bisect import bisect_left
input = lambda : sys.stdin.readline().rstrip()
out = []
B = 63

def popcount(x):
    x = (x & 6148914691236517205) + (x >> 1 & 6148914691236517205)
    x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
    x = (x & 1085102592571150095) + (x >> 4 & 1085102592571150095)
    x = (x & 71777214294589695) + (x >> 8 & 71777214294589695)
    x = (x & 281470681808895) + (x >> 16 & 281470681808895)
    x = (x & 4294967295) + (x >> 32 & 4294967295)
    return x
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    A = list(map(int, input().split()))
    G = [[] for _ in range(n)]
    for _ in range(m):
        (v, u) = map(int, input().split())
        G[u - 1].append(v - 1)
        G[v - 1].append(u - 1)
    A = [len(G[i]) - a for (i, a) in enumerate(A)]
    Q = [i for (i, a) in enumerate(A) if a == 0]
    for i in range(n):
        u = Q[i]
        g = []
        for v in G[u]:
            if A[v]:
                g.append(v)
                A[v] -= 1
                if not A[v]:
                    Q.append(v)
        G[u] = g
    pos = [0] * n
    for (i, u) in enumerate(Q):
        pos[u] = i
    X = []
    Y = []
    for (i, u) in enumerate(Q):
        for v in G[u]:
            X.append(i)
            Y.append(pos[v])
    ans = n * (n + 1) // 2
    mask = [0] * n
    for l in range(0, n, B):
        r = min(n, l + B)
        for i in range(l, r):
            mask[i] = 1 << i - l
        for (u, v) in zip(X, Y):
            mask[v] |= mask[u]
        for i in range(l, n):
            ans -= popcount(mask[i])
            mask[i] = 0
    out.append(ans)
print('\n'.join(map(str, out)))

Solution (Python):
import sys
from bisect import bisect_left
input = lambda : sys.stdin.readline().rstrip()
out = []
B = 63

def popcount(x):
    x = (x & 6148914691236517205) + (x >> 1 & 6148914691236517205)
    x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
    x = (x & 1085102592571150095) + (x >> 4 & 1085102592571150095)
    x = (x & 71777214294589695) + (x >> 8 & 71777214294589695)
    x = (x & 281470681808895) + (x >> 16 & 281470681808895)
    x = (x & 4294967295) + (x >> 32 & 4294967295)
    return x
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    A = list(map(int, input().split()))
    G = [[] for _ in range(n)]
    for _ in range(m):
        (v, u) = map(int, input().split())
        G[u - 1].append(v - 1)
        G[v - 1].append(u - 1)
    A = [len(G[i]) - a for (i, a) in enumerate(A)]
    Q = [i for (i, a) in enumerate(A) if a == 0]
    for i in range(n):
        u = Q[i]
        g = []
        for v in G[u]:
            if A[v]:
                g.append(v)
                A[v] -= 1
                if not A[v]:
                    Q.append(v)
        G[u] = g
    pos = [0] * n
    for (i, u) in enumerate(Q):
        pos[u] = i
    X = []
    Y = []
    for (i, u) in enumerate(Q):
        for v in G[u]:
            X.append(i)
            Y.append(pos[v])
    ans = n * (n + 1) // 2
    mask = [0] * n
    for l in range(0, n, B):
        r = min(n, l + B)
        for i in range(l, r):
            mask[i] = 1 << i - l
        for (u, v) in zip(X, Y):
            mask[v] |= mask[u]
        for i in range(l, n):
            ans -= popcount(mask[i])
            mask[i] = 0
    out.append(ans)
print('\n'.join(map(str, out)))

Solution (Python):
import sys
from bisect import bisect_left
input = lambda : sys.stdin.readline().rstrip()
out = []
B = 63

def popcount(x):
    x = (x & 6148914691236517205) + (x >> 1 & 6148914691236517205)
    x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
    x = (x & 1085102592571150095) + (x >> 4 & 1085102592571150095)
    x = (x & 71777214294589695) + (x >> 8 & 71777214294589695)
    x = (x & 281470681808895) + (x >> 16 & 281470681808895)
    x = (x & 4294967295) + (x >> 32 & 4294967295)
    return x
for _ in range(int(input())):
    (n, m) = map(int, input().split())
    A = list(map(int, input().split()))
    G = [[] for _ in range(n)]
    for _ in range(m):
        (v, u) = map(int, input().split())
        G[u - 1].append(v - 1)
        G[v - 1].append(u - 1)
    A = [len(G[i]) - a for (i, a) in enumerate(A)]
    removed = [False] * n
    Q = [i for (i, a) in enumerate(A) if a == 0]
    for i in range(n):
        u = Q[i]
        removed[u] = True
        g = []
        for v in G[u]:
            if not removed[v]:
                g.append(v)
                A[v] -= 1
                if A[v] == 0:
                    Q.append(v)
        G[u] = g
    pos = [0] * n
    for (i, u) in enumerate(Q):
        pos[u] = i
    X = []
    Y = []
    for (i, u) in enumerate(Q):
        for v in G[u]:
            X.append(i)
            Y.append(pos[v])
    ans = n * (n + 1) // 2
    mask = [0] * n
    for l in range(0, n, B):
        r = min(n, l + B)
        for i in range(l, r):
            mask[i] = 1 << i - l
        j = bisect_left(X, l)
        (X, Y) = (X[j:], Y[j:])
        for (u, v) in zip(X, Y):
            mask[v] |= mask[u]
        for i in range(l, n):
            ans -= popcount(mask[i])
            mask[i] = 0
    out.append(ans)
print('\n'.join(map(str, out)))