結果

問題 No.1813 Magical Stones
ユーザー 草苺奶昔
提出日時 2023-03-15 14:05:24
言語 Go
(1.23.4)
結果
AC  
実行時間 372 ms / 2,000 ms
コード長 3,555 bytes
コンパイル時間 12,667 ms
コンパイル使用メモリ 232,508 KB
実行使用メモリ 45,368 KB
最終ジャッジ日時 2024-09-18 08:44:18
合計ジャッジ時間 20,667 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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)
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0