結果

問題 No.2290 UnUnion Find
ユーザー ynm3nynm3n
提出日時 2023-05-06 01:13:34
言語 Go
(1.22.1)
結果
AC  
実行時間 909 ms / 2,000 ms
コード長 1,991 bytes
コンパイル時間 14,126 ms
コンパイル使用メモリ 240,008 KB
実行使用メモリ 9,600 KB
最終ジャッジ日時 2024-05-02 19:46:33
合計ジャッジ時間 37,430 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 222 ms
5,376 KB
testcase_03 AC 315 ms
6,528 KB
testcase_04 AC 322 ms
6,528 KB
testcase_05 AC 323 ms
6,604 KB
testcase_06 AC 324 ms
6,528 KB
testcase_07 AC 323 ms
6,528 KB
testcase_08 AC 328 ms
6,528 KB
testcase_09 AC 329 ms
6,528 KB
testcase_10 AC 331 ms
6,624 KB
testcase_11 AC 334 ms
6,656 KB
testcase_12 AC 334 ms
6,528 KB
testcase_13 AC 332 ms
6,528 KB
testcase_14 AC 337 ms
6,528 KB
testcase_15 AC 337 ms
6,528 KB
testcase_16 AC 332 ms
6,528 KB
testcase_17 AC 332 ms
6,528 KB
testcase_18 AC 332 ms
6,528 KB
testcase_19 AC 265 ms
8,192 KB
testcase_20 AC 271 ms
9,600 KB
testcase_21 AC 295 ms
6,528 KB
testcase_22 AC 909 ms
6,556 KB
testcase_23 AC 905 ms
6,548 KB
testcase_24 AC 267 ms
8,704 KB
testcase_25 AC 734 ms
6,596 KB
testcase_26 AC 274 ms
9,088 KB
testcase_27 AC 271 ms
8,832 KB
testcase_28 AC 249 ms
5,760 KB
testcase_29 AC 268 ms
8,576 KB
testcase_30 AC 337 ms
6,528 KB
testcase_31 AC 268 ms
8,320 KB
testcase_32 AC 762 ms
6,540 KB
testcase_33 AC 250 ms
5,632 KB
testcase_34 AC 272 ms
9,600 KB
testcase_35 AC 270 ms
9,088 KB
testcase_36 AC 859 ms
6,576 KB
testcase_37 AC 245 ms
5,504 KB
testcase_38 AC 862 ms
6,552 KB
testcase_39 AC 842 ms
6,528 KB
testcase_40 AC 269 ms
8,960 KB
testcase_41 AC 683 ms
6,528 KB
testcase_42 AC 265 ms
8,064 KB
testcase_43 AC 254 ms
6,016 KB
testcase_44 AC 332 ms
6,528 KB
testcase_45 AC 309 ms
7,424 KB
testcase_46 AC 316 ms
7,416 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	rd := bufio.NewReader(os.Stdin)
	wr := bufio.NewWriter(os.Stdout)
	defer wr.Flush()

	var n, q int
	fmt.Fscan(rd, &n, &q)

	uf := newUnionFindTree(n)
	var typ, u, v int
	for i := 0; i < q; i++ {
		if len(uf.roots) < n/100 {
			next := make(map[int]struct{}, len(uf.roots))
			for i := range uf.roots {
				next[i] = struct{}{}
			}
			uf.roots = next
		}
		fmt.Fscan(rd, &typ)
		switch typ {
		case 1:
			fmt.Fscan(rd, &u, &v)
			u--
			v--
			uf.unite(u, v)
		case 2:
			fmt.Fscan(rd, &v)
			v--
			r := uf.findRoot(v)
			ans := -1
			for v2 := range uf.roots {
				if r != v2 {
					ans = v2 + 1
					break
				}
			}
			fmt.Fprintln(wr, ans)
		}
	}
}

// UnionFind Tree
type unionFindTree struct {
	// 備忘録
	// 根となる頂点の要素には、特別に以下のような数値が格納されています。
	// 「その根が含まれている木」に含まれる頂点の数にマイナスをかけたもの
	parent []int
	// 連結成分の個数です
	cnt int

	roots map[int]struct{}
}

func newUnionFindTree(n int) *unionFindTree {
	uf := new(unionFindTree)
	uf.parent = make([]int, n)
	for i := range uf.parent {
		uf.parent[i] = -1
	}
	uf.cnt = n
	uf.roots = make(map[int]struct{}, n)
	for i := 0; i < n; i++ {
		uf.roots[i] = struct{}{}
	}
	return uf
}
func (uf *unionFindTree) findRoot(a int) int {
	if uf.parent[a] < 0 {
		return a
	}
	r := uf.findRoot(uf.parent[a])
	if _, exist := uf.roots[a]; exist && a != r {
		delete(uf.roots, a)
	}
	uf.parent[a] = r
	return r
}
func (uf *unionFindTree) unite(a, b int) bool {
	x, y := uf.findRoot(a), uf.findRoot(b)
	if x == y {
		return false
	}
	if uf.size(x) < uf.size(y) {
		x, y = y, x
	}
	delete(uf.roots, y)
	uf.parent[x] += uf.parent[y]
	uf.parent[y] = x
	uf.cnt--
	return true
}
func (uf *unionFindTree) sameRoot(a, b int) bool {
	return uf.findRoot(a) == uf.findRoot(b)
}
func (uf *unionFindTree) size(a int) int {
	return -uf.parent[uf.findRoot(a)]
}
0