Monsters (Codeforces 1810E)
Tags: Greedy, dsu

There is an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. Initially, for each vertex $$$i$$$, there is a monster with danger $$$a_{i}$$$ on that vertex. For a monster with danger $$$a_{i}$$$, you can defeat it if and only if you have defeated at least $$$a_{i}$$$ other monsters before.Now you want to defeat all the monsters. First, you choose some vertex $$$s$$$ and defeat the monster on that vertex (since you haven't defeated any monsters before, $$$a_{s}$$$ has to be $$$0$$$). Then, you can move through the edges. If you want to move from vertex $$$u$$$ to vertex $$$v$$$, then the following must hold: either the monster on vertex $$$v$$$ has been defeated before, or you can defeat it now. For the second case, you defeat the monster on vertex $$$v$$$ and reach vertex $$$v$$$.You can pass the vertices and the edges any number of times. Determine whether you can defeat all the monsters or not.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Their description follows.The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of vertices and edges in the graph respectively. The second line of each test case contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$0 \le a_{i} \le n$$$) — the dangers of monsters on corresponding vertices.For the following $$$m$$$ lines, each line contains two integers $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n$$$), describing an edge connecting vertex $$$u$$$ and vertex $$$v$$$. It is guaranteed that there are no multi-edges or self-loops in the graph.It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output "YES" if you can defeat all the monsters, or "NO" otherwise.You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Note: In the first test case, you can start at vertex $$$3$$$ and defeat the monster on it, before you go to vertices $$$2$$$, $$$1$$$ in this order, defeating the monsters on them as well. Then you return to vertex $$$3$$$, and go to vertex $$$4$$$, defeating the monster on it.In the third test case, there is no path to vertex $$$4$$$ if you start at vertex $$$1$$$. Also, there is no path to vertices $$$1$$$, $$$2$$$, and $$$3$$$ if you start at vertex $$$4$$$.

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

Sample Outputs:
YES
YES
NO
YES
NO

Solution (Python):
class DSU:

    def __init__(self, n):
        self.f = list(range(n))
        self.siz = [1] * n

    def leader(self, x):
        while x != self.f[x]:
            self.f[x] = self.f[self.f[x]]
            x = self.f[x]
        return x

    def same(self, x, y):
        return self.leader(x) == self.leader(y)

    def merge(self, x, y):
        x = self.leader(x)
        y = self.leader(y)
        if x == y:
            return False
        self.siz[x] += self.siz[y]
        self.f[y] = x
        return True

    def size(self, x):
        return self.siz[self.leader(x)]

def solve():
    (n, m) = map(int, input().split())
    a = list(map(int, input().split()))
    adj = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(int, input().split())
        u -= 1
        v -= 1
        if (a[u], u) < (a[v], v):
            (u, v) = (v, u)
        adj[u].append(v)
    ok = [False] * n
    order = list(range(n))
    order.sort(key=lambda i: (a[i], i))
    dsu = DSU(n)
    for x in order:
        ok[x] = a[x] == 0
        for y in adj[x]:
            y = dsu.leader(y)
            if ok[y] and dsu.size(y) >= a[x]:
                ok[x] = True
            dsu.merge(x, y)
    for i in range(n):
        if not dsu.same(0, i):
            print('NO')
            return
    if ok[dsu.leader(0)]:
        print('YES')
    else:
        print('NO')
for _ in range(int(input())):
    solve()

Solution (Python):
from functools import reduce
import heapq
g = {}
vis = []
frontier = []

def expand_bfs(s):
    q = [s]
    kill_count = 1
    continuous_fail_count = 0
    strong_monster_count = 0
    unvisited_flag = s + 1
    visited_flag = -s
    while len(q) != 0:
        if continuous_fail_count == len(q):
            break
        v = q.pop(0)
        if vis[v - 1] == unvisited_flag:
            strong_monster_count -= 1
        vis[v - 1] = visited_flag
        all_visited = True
        for next in g[v]:
            if vis[next - 1] != visited_flag and monsters[next - 1] <= kill_count:
                q.append(next)
                kill_count += 1
            elif monsters[next - 1] > kill_count:
                vis[next - 1] = unvisited_flag
                strong_monster_count += 1
                all_visited = False
        if not all_visited:
            q.append(v)
            continuous_fail_count += 1
        else:
            continuous_fail_count = 0
    return strong_monster_count

def solve_with_bfs():
    for s in frontier:
        if vis[s - 1] == 0 and s in g:
            count = expand_bfs(s)
            if count == 0:
                break
    f = vis[0]
    v = reduce(lambda a, b: a and b == f, vis, True)
    return f != 0 and v

def compress_graph(g):
    return '|'.join(['{}:{}'.format(i, ','.join([str(s) for s in g[i]])) for i in g])

def trySorted(s):
    q = []
    heapq.heappush(q, (0, s))
    visited_flag = s
    vis[s - 1] = visited_flag
    kill_count = 0
    while len(q) != 0:
        (monster_strength, node) = heapq.heappop(q)
        if monster_strength > kill_count:
            return 0
        kill_count += 1
        for next in g[node]:
            if vis[next - 1] != visited_flag:
                heapq.heappush(q, (monsters[next - 1], next))
                vis[next - 1] = visited_flag
    return kill_count

def display_graph(s):
    for i in g:
        print('({})[{}]: {}'.format(i, monsters[i - 1], ' ,'.join(['({})[{}]'.format(s, monsters[s - 1]) for s in g[i]])))

def solve_sorted():
    for s in frontier:
        if vis[s - 1] == 0 and s in g:
            kill_count = trySorted(s)
            if kill_count == n:
                return True
    return False
if __name__ == '__main__':
    t = int(input())
    for test_case in range(1, t + 1):
        (n, m) = [int(u) for u in input().split(' ')]
        monsters = [int(u) for u in input().split(' ')]
        g = {}
        frontier = []
        for (idx, x) in enumerate(monsters):
            if x == 0:
                frontier.append(idx + 1)
        vis = [0 for i in range(n)]
        for i in range(m):
            (s, e) = [int(u) for u in input().split(' ')]
            if s in g:
                g[s].append(e)
            else:
                g[s] = [e]
            if e in g:
                g[e].append(s)
            else:
                g[e] = [s]
        f = solve_sorted()
        print('{}'.format('YES' if f else 'NO'))

Solution (Python):
import heapq

def read_data():
    (n, m) = map(int, input().strip().split())
    danger = list(map(int, input().strip().split()))
    graph = {}
    for _ in range(m):
        (x, y) = map(lambda x: int(x) - 1, input().strip().split())
        if x not in graph:
            graph[x] = []
        graph[x].append(y)
        if y not in graph:
            graph[y] = []
        graph[y].append(x)
    return (n, m, danger, graph)

def dfs(v: int, graph: dict, danger, n, vis):
    stack = [(danger[v], v)]
    c = 0
    pp = set()
    while stack:
        (_, u) = heapq.heappop(stack)
        vis[u] = v
        if danger[u] > c:
            return c == n
        if u in pp:
            continue
        c += 1
        pp.add(u)
        if c == n:
            return True
        for p in graph[u]:
            if vis[p] != v:
                heapq.heappush(stack, (danger[p], p))
    return c == n

def solve():
    (n, _, danger, graph) = read_data()
    vis = [-1 for _ in range(n)]
    for i in range(n):
        if i not in graph:
            print('NO')
            return
        if danger[i] == 0 and vis[i] == -1:
            if dfs(i, graph, danger, n, vis):
                print('YES')
                return
    print('NO')

def main():
    for _ in range(int(input())):
        solve()
if __name__ == '__main__':
    main()