結果

問題 No.1813 Magical Stones
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-15 14:05:24
言語 Go
(1.22.1)
結果
AC  
実行時間 370 ms / 2,000 ms
コード長 3,555 bytes
コンパイル時間 11,784 ms
コンパイル使用メモリ 211,220 KB
実行使用メモリ 47,468 KB
最終ジャッジ日時 2023-10-18 12:23:22
合計ジャッジ時間 21,001 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 12 ms
12,120 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 1 ms
4,348 KB
testcase_06 AC 4 ms
4,348 KB
testcase_07 AC 1 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 54 ms
12,228 KB
testcase_12 AC 2 ms
4,348 KB
testcase_13 AC 1 ms
4,348 KB
testcase_14 AC 12 ms
12,116 KB
testcase_15 AC 370 ms
47,108 KB
testcase_16 AC 368 ms
46,920 KB
testcase_17 AC 349 ms
41,852 KB
testcase_18 AC 362 ms
41,096 KB
testcase_19 AC 365 ms
40,644 KB
testcase_20 AC 363 ms
47,468 KB
testcase_21 AC 365 ms
40,952 KB
testcase_22 AC 361 ms
43,580 KB
testcase_23 AC 364 ms
40,840 KB
testcase_24 AC 4 ms
4,348 KB
testcase_25 AC 29 ms
8,448 KB
testcase_26 AC 9 ms
4,348 KB
testcase_27 AC 244 ms
30,056 KB
testcase_28 AC 317 ms
37,792 KB
testcase_29 AC 295 ms
33,520 KB
testcase_30 AC 283 ms
34,732 KB
testcase_31 AC 338 ms
43,608 KB
testcase_32 AC 1 ms
4,348 KB
testcase_33 AC 1 ms
4,348 KB
testcase_34 AC 10 ms
5,632 KB
testcase_35 AC 38 ms
8,160 KB
testcase_36 AC 4 ms
4,348 KB
testcase_37 AC 89 ms
16,676 KB
testcase_38 AC 28 ms
15,676 KB
testcase_39 AC 223 ms
26,808 KB
testcase_40 AC 6 ms
5,632 KB
testcase_41 AC 11 ms
5,656 KB
testcase_42 AC 41 ms
8,188 KB
testcase_43 AC 21 ms
7,760 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

func main() {
	// https://yukicoder.me/problems/no/1813
	// 不等关系:有向边
	// 给定一个DAG 求将DAG变为一个环(强连通分量)的最少需要添加的边数
	// !答案为 `max(入度为0的点的个数, 出度为0的点的个数)`

	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m int
	fmt.Fscan(in, &n, &m)

	scc := NewStronglyConnectedComponents(n)
	for i := 0; i < m; i++ {
		var u, v int
		fmt.Fscan(in, &u, &v)
		scc.AddEdge(u-1, v-1, 1)
	}
	scc.Build()

	if len(scc.Group) == 1 { // 缩成一个点了,说明是强连通的
		fmt.Fprintln(out, 0)
		return
	}

	g := len(scc.Group)
	indeg, outDeg := make([]int, g), make([]int, g)
	for i := 0; i < g; i++ {
		for _, next := range scc.Dag[i] {
			indeg[next]++
			outDeg[i]++
		}
	}

	in0, out0 := 0, 0
	for i := 0; i < g; i++ {
		if indeg[i] == 0 {
			in0++
		}
		if outDeg[i] == 0 {
			out0++
		}
	}

	fmt.Fprintln(out, max(in0, out0))
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

type WeightedEdge struct{ from, to, cost, index int }
type StronglyConnectedComponents struct {
	G      [][]WeightedEdge // 原图
	Dag    [][]int          // 强连通分量缩点后的DAG(有向图邻接表)
	CompId []int            // 每个顶点所属的强连通分量的编号
	Group  [][]int          // 每个强连通分量所包含的顶点
	rg     [][]WeightedEdge
	order  []int
	used   []bool
	eid    int
}

func NewStronglyConnectedComponents(n int) *StronglyConnectedComponents {
	return &StronglyConnectedComponents{G: make([][]WeightedEdge, n)}
}

func (scc *StronglyConnectedComponents) AddEdge(from, to, cost int) {
	scc.G[from] = append(scc.G[from], WeightedEdge{from, to, cost, scc.eid})
	scc.eid++
}

func (scc *StronglyConnectedComponents) Build() {
	scc.rg = make([][]WeightedEdge, len(scc.G))
	for i := range scc.G {
		for _, e := range scc.G[i] {
			scc.rg[e.to] = append(scc.rg[e.to], WeightedEdge{e.to, e.from, e.cost, e.index})
		}
	}

	scc.CompId = make([]int, len(scc.G))
	for i := range scc.CompId {
		scc.CompId[i] = -1
	}
	scc.used = make([]bool, len(scc.G))
	for i := range scc.G {
		scc.dfs(i)
	}
	for i, j := 0, len(scc.order)-1; i < j; i, j = i+1, j-1 {
		scc.order[i], scc.order[j] = scc.order[j], scc.order[i]
	}

	ptr := 0
	for _, v := range scc.order {
		if scc.CompId[v] == -1 {
			scc.rdfs(v, ptr)
			ptr++
		}
	}

	dag := make([][]int, ptr)
	visited := make(map[int]struct{}) // 边去重
	for i := range scc.G {
		for _, e := range scc.G[i] {
			x, y := scc.CompId[e.from], scc.CompId[e.to]
			if x == y {
				continue // 原来的边 x->y 的顶点在同一个强连通分量内,可以汇合同一个 SCC 的权值
			}
			hash := x*len(scc.G) + y
			if _, ok := visited[hash]; !ok {
				dag[x] = append(dag[x], y)
				visited[hash] = struct{}{}
			}
		}
	}
	scc.Dag = dag

	scc.Group = make([][]int, ptr)
	for i := range scc.G {
		scc.Group[scc.CompId[i]] = append(scc.Group[scc.CompId[i]], i)
	}
}

// 获取顶点k所属的强连通分量的编号
func (scc *StronglyConnectedComponents) Get(k int) int {
	return scc.CompId[k]
}

func (scc *StronglyConnectedComponents) dfs(idx int) {
	tmp := scc.used[idx]
	scc.used[idx] = true
	if tmp {
		return
	}
	for _, e := range scc.G[idx] {
		scc.dfs(e.to)
	}
	scc.order = append(scc.order, idx)
}

func (scc *StronglyConnectedComponents) rdfs(idx int, cnt int) {
	if scc.CompId[idx] != -1 {
		return
	}
	scc.CompId[idx] = cnt
	for _, e := range scc.rg[idx] {
		scc.rdfs(e.to, cnt)
	}
}
0