Trips (Codeforces 1037E)
Tags: Others, graphs

There are $$$n$$$ persons who initially don't know each other. On each morning, two of them, who were not friends before, become friends.We want to plan a trip for every evening of $$$m$$$ days. On each trip, you have to select a group of people that will go on the trip. For every person, one of the following should hold:   Either this person does not go on the trip,  Or at least $$$k$$$ of his friends also go on the trip. Note that the friendship is not transitive. That is, if $$$a$$$ and $$$b$$$ are friends and $$$b$$$ and $$$c$$$ are friends, it does not necessarily imply that $$$a$$$ and $$$c$$$ are friends.For each day, find the maximum number of people that can go on the trip on that day.

Input: The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5$$$, $$$1 \le k < n$$$) — the number of people, the number of days and the number of friends each person on the trip should have in the group.The $$$i$$$-th ($$$1 \leq i \leq m$$$) of the next $$$m$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1\leq x, y\leq n$$$, $$$x\ne y$$$), meaning that persons $$$x$$$ and $$$y$$$ become friends on the morning of day $$$i$$$. It is guaranteed that $$$x$$$ and $$$y$$$ were not friends before.

Output: Print exactly $$$m$$$ lines, where the $$$i$$$-th of them ($$$1\leq i\leq m$$$) contains the maximum number of people that can go on the trip on the evening of the day $$$i$$$.

Note: In the first example,   $$$1,2,3$$$ can go on day $$$3$$$ and $$$4$$$. In the second example,   $$$2,4,5$$$ can go on day $$$4$$$ and $$$5$$$.  $$$1,2,4,5$$$ can go on day $$$6$$$ and $$$7$$$.  $$$1,2,3,4,5$$$ can go on day $$$8$$$. In the third example,   $$$1,2,5$$$ can go on day $$$5$$$.  $$$1,2,3,5$$$ can go on day $$$6$$$ and $$$7$$$. 

Sample Inputs:
4 4 2
2 3
1 2
1 3
1 4

5 8 2
2 1
4 2
5 4
5 2
4 3
5 1
4 1
3 2

5 7 2
1 5
3 2
2 5
3 4
1 2
5 3
1 3

Sample Outputs:
0
0
3
3

0
0
0
3
3
4
4
5

0
0
0
0
3
4
4

Solution (Python):
from collections import deque

def solve(adj, m, k, uv):
    n = len(adj)
    nn = [len(a) for a in adj]
    q = deque()
    for i in range(n):
        if nn[i] < k:
            q.append(i)
    while q:
        v = q.popleft()
        for u in adj[v]:
            nn[u] -= 1
            if nn[u] == k - 1:
                q.append(u)
    res = [0] * m
    nk = len([1 for i in nn if i >= k])
    res[-1] = nk
    for i in range(m - 1, 0, -1):
        (u1, v1) = uv[i]
        if nn[u1] < k or nn[v1] < k:
            res[i - 1] = nk
            continue
        if nn[u1] == k:
            q.append(u1)
            nn[u1] -= 1
        if not q and nn[v1] == k:
            q.append(v1)
            nn[v1] -= 1
        if not q:
            nn[u1] -= 1
            nn[v1] -= 1
            adj[u1].remove(v1)
            adj[v1].remove(u1)
        while q:
            v = q.popleft()
            nk -= 1
            for u in adj[v]:
                nn[u] -= 1
                if nn[u] == k - 1:
                    q.append(u)
        res[i - 1] = nk
    return res
(n, m, k) = map(int, input().split())
a = [set() for i in range(n)]
uv = []
for i in range(m):
    (u, v) = map(int, input().split())
    a[u - 1].add(v - 1)
    a[v - 1].add(u - 1)
    uv.append((u - 1, v - 1))
res = solve(a, m, k, uv)
print(str(res)[1:-1].replace(' ', '').replace(',', '\n'))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def bfs():
    global l
    while len(q) ^ l:
        i = q[l]
        for j in G[i]:
            ng.add((i, j))
            ng.add((j, i))
            G[j].remove(i)
            if len(G[j]) < k and (not visit[j]):
                q.append(j)
                visit[j] = 1
        G[i].clear()
        l += 1
(n, m, k) = map(int, input().split())
ans = []
G = [set() for _ in range(n + 1)]
xy = [tuple(map(int, input().split())) for _ in range(m)]
for (x, y) in xy:
    G[x].add(y)
    G[y].add(x)
q = []
visit = [0] * (n + 1)
for i in range(1, n + 1):
    if len(G[i]) < k:
        q.append(i)
        visit[i] = 1
l = 0
ng = set()
bfs()
ans = []
for (x, y) in xy[::-1]:
    ans0 = n - l
    ans.append(ans0)
    if (x, y) in ng:
        continue
    G[x].remove(y)
    G[y].remove(x)
    if len(G[x]) < k and (not visit[x]):
        q.append(x)
    if len(G[y]) < k and (not visit[y]):
        q.append(y)
    bfs()
sys.stdout.write('\n'.join(map(str, ans[::-1])))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
import heapq

def process(n, G, k):
    m = len(G)
    g = [[] for i in range(n + 1)]
    for i in range(m):
        (u, v) = G[i]
        g[u].append((v, i))
        g[v].append((u, i))
    degrees = [len(g[i]) for i in range(n + 1)]
    removed = [1 for i in range(n + 1)]
    removed[0] = 0
    H = []
    for i in range(1, n + 1):
        heapq.heappush(H, (degrees[i], i))
    while len(H) > 0:
        (d_u, u) = H[0]
        if degrees[u] != d_u:
            heapq.heappop(H)
        elif d_u < k:
            heapq.heappop(H)
            removed[u] = 0
            for (v, j) in g[u]:
                if removed[v] == 1:
                    degrees[v] -= 1
                    heapq.heappush(H, (degrees[v], v))
        else:
            break
    for u in range(1, n + 1):
        if removed[u] == 0:
            g[u] = []
        else:
            g[u] = [v for v in g[u] if removed[v[0]] == 1]
    golden = sum(removed)
    answer = [0 for i in range(m)]
    answer[-1] = golden
    for i in range(m - 1, -1, -1):
        (u, v) = G[i]
        if removed[u] == 1 and removed[v] == 1:
            degrees[u] -= 1
            degrees[v] -= 1
            heapq.heappush(H, (degrees[u], u))
            heapq.heappush(H, (degrees[v], v))
            while len(H) > 0:
                (d_x, x) = H[0]
                if degrees[x] != d_x:
                    heapq.heappop(H)
                elif d_x < k:
                    heapq.heappop(H)
                    if removed[x] == 1:
                        golden -= 1
                        removed[x] = 0
                        for (y, i1) in g[x]:
                            if i1 < i and removed[y] == 1:
                                degrees[y] -= 1
                                heapq.heappush(H, (degrees[y], y))
                else:
                    break
        if i > 0:
            answer[i - 1] = golden
    for i in range(m):
        sys.stdout.write(f'{answer[i]}\n')
(n, m, k) = [int(x) for x in input().split()]
G = []
for i in range(m):
    (u, v) = [int(x) for x in input().split()]
    G.append([u, v])
process(n, G, k)