Advertisement
Ladies_Man

Число мостов - Bridge number

Apr 12th, 2014
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Go 1.59 KB | None | 0 0
  1. package main
  2. import "fmt"
  3. //import "github.com/skorobogatov/input"
  4.  
  5. type vertex struct {
  6.         x      int
  7.     mark   string
  8.     comp   int
  9.     edge   []*vertex
  10.     parent *vertex
  11. }
  12.  
  13. func main() {
  14.     var i, n, m, v, u, comp_dfs1, comp_dfs2, t_c int
  15.     var VisitVertex2 func(v *vertex, component int)
  16.     var VisitVertex1 func(v *vertex) int
  17.     var queue [](*vertex)
  18.  
  19.     fmt.Scanf("%d\n", &n)
  20.     fmt.Scanf("%d\n", &m)
  21.    
  22.     list := make([]vertex, n)
  23.  
  24.     for i < m {
  25.         fmt.Scanf("%d %d\n", &u, &v)
  26.         list[u].edge, list[v].edge = append(list[u].edge, &list[v]), append(list[v].edge, &list[u])
  27.         i++
  28.     }
  29.  
  30.     Enqueue := func(Q [](*vertex), vert *vertex) []*vertex { return append(Q, vert) }
  31.     Dequeue := func(Q [](*vertex), num int) *vertex { return Q[num] }
  32.    
  33.     VisitVertex1 = func(v *vertex) {
  34.         E_G := v.edge
  35.         v.mark = "gray"
  36.         queue = Enqueue(queue, v)
  37.         for i, _ := range E_G {
  38.             u := E_G[i]
  39.             if u.mark == "white" {
  40.                 u.parent = v
  41.                 VisitVertex1(u)
  42.             }
  43.         }
  44.         v.mark = "black"
  45.     }
  46.  
  47.     VisitVertex2 = func(v *vertex, component int) {
  48.         v.comp = component
  49.         E_G := v.edge
  50.         for i, _ := range E_G {
  51.             u := E_G[i]
  52.             if u.comp == -1 && u.parent != v { VisitVertex2(u, component) }
  53.         }
  54.     }
  55.     V_G := list
  56. //DFS1
  57.     for i, _ := range V_G { V_G[i].mark = "white" }
  58.     for i, _ := range V_G {
  59.         v := V_G[i]
  60.         if v.mark == "white" {
  61.             VisitVertex1(&v)
  62.             comp_dfs1++
  63.         }
  64.     }
  65. //DFS2
  66.     for i, _ := range V_G { V_G[i].comp = -1 }
  67.     for i, _ := range queue {
  68.         v := Dequeue(queue, i)
  69.         if v.comp == -1 {
  70.             VisitVertex2(v, comp_dfs2)
  71.             comp_dfs2++
  72.         }
  73.     }
  74.     fmt.Printf("comp=%d\n", comp_dfs2-comp_dfs1)
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement