Submission #64781262

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n, m = map(int, input().split())
edg = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))  # 各要素の親（初期状態では自分自身）
        self.rank = [0] * n           # ランク（経路圧縮用）
    def find(self, x):
        # 経路圧縮を行いながら親を探す
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def unite(self, x, y):
        # xとyの代表を見つける
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return  # すでに同じグループ
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

n, m = map(int, input().split())
edg = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))  # 各要素の親（初期状態では自分自身）
        self.rank = [0] * n           # ランク（経路圧縮用）

    def find(self, x):
        # 経路圧縮を行いながら親を探す
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        # xとyの代表を見つける
        x_root = self.find(x)
        y_root = self.find(y)

        if x_root == y_root:
            return  # すでに同じグループ

        # 小さい方の番号を代表とする
        if x_root < y_root:
            self.parent[y_root] = x_root
        else:
            self.parent[x_root] = y_root

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

    def groups(self):
        # 各グループのメンバーをリスト化（確認用）
        from collections import defaultdict
        group_map = defaultdict(list)
        for i in range(len(self.parent)):
            root = self.find(i)
            group_map[root].append(i)
        return list(group_map.values())

for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    if u > v:
        u, v = v, u
    edg[u].append(v)
    rev[v].append(u)
ans = []
uf = DSU(n)
length = set()
gg=[1 for _ in range(n)]
for i in range(n):
    if i:
        for v in rev[i]:
            ul=uf.find(i)
            uk=uf.find(v)
            if ul>uk:
                ul,uk=uk,ul
            if ul!=uk:
                gg[ul]+=gg[uk]
                gg[uk]=0
            uf.unite(i, v)
            if v in length:
                length.discard(v)
            if i in length:
              length.discard(i)
              
    for v in edg[i]:
        length.add(v)
    if gg[0]==i+1:
        #print(length)
        ans.append(len(length))
    else:
        ans.append(-1)
print(*ans, sep="\n")

Submission Info

Judge Result