EWTD

4-structured

Sep 19th, 2021
872
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import "fmt"
  4. type Vertex struct {
  5.     edges []int
  6.     tin int
  7.     fup int
  8.     used bool
  9. }
  10.  
  11. func filling_edge(m int, g []Vertex)  {
  12.     for i:=0; i < m; i++{
  13.         a := 0; b:= 0
  14.         fmt.Scan(&a,&b)
  15.         g[a].edges = append(g[a].edges,b)
  16.         if a == b{
  17.             continue
  18.         }else{
  19.             g[b].edges = append(g[b].edges,a)
  20.         }
  21.     }
  22. }
  23.  
  24. func init_graph(g []Vertex)  {
  25.     for i:=0; i < len(g); i++{
  26.         g[i].used = false
  27.         g[i].tin = 0
  28.         g[i].fup = 0
  29.     }
  30. }
  31.  
  32.  
  33. func min(lhs, rhs int) int{
  34.     if lhs < rhs{
  35.         return lhs
  36.     }else{
  37.         return rhs
  38.     }
  39. }
  40.  
  41. func main(){
  42.     var bridge, time, n, m int
  43.     var DfsInner func(v,anc int)
  44.     fmt.Scan(&n,&m)
  45.     bridge = 0
  46.     time = 1
  47.     Graph := make([]Vertex,n)
  48.     init_graph(Graph)
  49.     DfsInner = func(v, anc int) {
  50.         Graph[v].used = true
  51.         Graph[v].tin = time; Graph[v].fup = time; time++
  52.         for _,to := range Graph[v].edges{
  53.             if to == anc{
  54.                 continue
  55.             }
  56.             if !Graph[to].used{
  57.                 DfsInner(to,v)
  58.                 Graph[v].fup = min(Graph[v].fup, Graph[to].fup)
  59.                 if Graph[to].fup > Graph[v].tin{bridge++}
  60.             }else{
  61.                 Graph[v].fup = min(Graph[v].fup,Graph[to].tin)
  62.             }
  63.         }
  64.     }
  65.     filling_edge(m,Graph)
  66.     for i:=0;i<n; i++ {if !Graph[i].used{DfsInner(i,-1)}}
  67.  
  68.    
  69.     fmt.Printf("%d\n",bridge)
  70. }
RAW Paste Data