結果

問題 No.1293 2種類の道路
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-12 10:41:42
言語 Go
(1.22.1)
結果
AC  
実行時間 579 ms / 2,000 ms
コード長 3,373 bytes
コンパイル時間 11,831 ms
コンパイル使用メモリ 216,148 KB
実行使用メモリ 92,680 KB
最終ジャッジ日時 2023-10-18 10:31:06
合計ジャッジ時間 18,619 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 1 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 1 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 566 ms
92,656 KB
testcase_10 AC 579 ms
90,492 KB
testcase_11 AC 568 ms
92,652 KB
testcase_12 AC 575 ms
92,680 KB
testcase_13 AC 574 ms
90,100 KB
testcase_14 AC 359 ms
82,148 KB
testcase_15 AC 367 ms
79,404 KB
testcase_16 AC 427 ms
90,028 KB
testcase_17 AC 425 ms
91,816 KB
testcase_18 AC 263 ms
64,564 KB
testcase_19 AC 356 ms
75,180 KB
testcase_20 AC 347 ms
73,108 KB
testcase_21 AC 217 ms
44,504 KB
testcase_22 AC 215 ms
44,476 KB
testcase_23 AC 210 ms
46,692 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

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

	var n, road1, road2 int
	fmt.Fscan(in, &n, &road1, &road2)
	scc := NewStronglyConnectedComponents(2 * n)
	for i := 0; i < road1; i++ {
		var a, b int
		fmt.Fscan(in, &a, &b)
		a, b = a-1, b-1
		scc.AddEdge(2*a, 2*b, 1)
		scc.AddEdge(2*b, 2*a, 1)
	}
	for i := 0; i < road2; i++ {
		var a, b int
		fmt.Fscan(in, &a, &b)
		a, b = a-1, b-1
		scc.AddEdge(2*a+1, 2*b+1, 1)
		scc.AddEdge(2*b+1, 2*a+1, 1)
	}
	for i := 0; i < n; i++ {
		scc.AddEdge(2*i, 2*i+1, 1)
	}
	scc.Build()

	v := len(scc.Group)
	dp := make([]int, v)
	for i := 0; i < n; i++ {
		dp[scc.CompId[2*i]]++
	}
	for i := 0; i < v; i++ {
		for _, e := range scc.Dag[i] {
			dp[e.to] += dp[e.from]
		}
	}

	res := 0
	for i := 0; i < n; i++ {
		res += dp[scc.CompId[2*i+1]] - 1 // !减去自己到自己的路径1
	}
	fmt.Fprintln(out, res)
}

type WeightedEdge struct{ from, to, cost, index int }
type StronglyConnectedComponents struct {
	G      [][]WeightedEdge // 原图
	Dag    [][]WeightedEdge // 强连通分量缩点后的顶点和边组成的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([][]WeightedEdge, 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
			}
			hash := x*len(scc.G) + y
			if _, ok := visited[hash]; !ok {
				dag[x] = append(dag[x], WeightedEdge{x, y, e.cost, e.index})
				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