結果
問題 | No.1293 2種類の道路 |
ユーザー |
|
提出日時 | 2023-03-12 10:41:42 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 515 ms / 2,000 ms |
コード長 | 3,373 bytes |
コンパイル時間 | 11,145 ms |
コンパイル使用メモリ | 235,888 KB |
実行使用メモリ | 92,032 KB |
最終ジャッジ日時 | 2024-09-18 06:58:00 |
合計ジャッジ時間 | 17,898 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
package mainimport ("bufio""fmt""os")func main() {in := bufio.NewReader(os.Stdin)out := bufio.NewWriter(os.Stdout)defer out.Flush()var n, road1, road2 intfmt.Fscan(in, &n, &road1, &road2)scc := NewStronglyConnectedComponents(2 * n)for i := 0; i < road1; i++ {var a, b intfmt.Fscan(in, &a, &b)a, b = a-1, b-1scc.AddEdge(2*a, 2*b, 1)scc.AddEdge(2*b, 2*a, 1)}for i := 0; i < road2; i++ {var a, b intfmt.Fscan(in, &a, &b)a, b = a-1, b-1scc.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 := 0for 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 // 强连通分量缩点后的顶点和边组成的DAGCompId []int // 每个顶点所属的强连通分量的编号Group [][]int // 每个强连通分量所包含的顶点rg [][]WeightedEdgeorder []intused []booleid 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 := 0for _, 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) + yif _, ok := visited[hash]; !ok {dag[x] = append(dag[x], WeightedEdge{x, y, e.cost, e.index})visited[hash] = struct{}{}}}}scc.Dag = dagscc.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] = trueif 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] = cntfor _, e := range scc.rg[idx] {scc.rdfs(e.to, cnt)}}