PAT:05-1. List Components (25),Go语言解答

go golang pat

题目大概意思:给定一个有N个顶点和E个边的无向图,请分别用DFS和BFS遍历无向图。假定顶点编号为0到N-1,在遍历的时候总是从最小编号的顶点出发,在访问相邻结点的时候,按升序的方式访问。

 

For a given undirected graph with N vertices and E edges, please list all the connected components by both DFS and BFS. Assume that all the vertices are numbered from 0 to N-1. While searching, assume that we always start from the vertex with the smallest index, and visit its adjacent vertices in ascending order of their indices.

Input Specification:

Each input file contains one test case. For each case, the first line gives two integers N (0

Output Specification:

For each test case, print in each line a connected component in the format "{ v1 v2 ... vk }". First print the result obtained by DFS, then by BFS.

Sample Input:

8 6
0 7
0 1
2 0
4 1
2 4
3 5

Sample Output:

{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
 
001 package main
002 
003 import (
004     "fmt"
005     "container/heap"
006     "container/list"
007 )
008 var visited = make([]bool, 10)//题目给出顶点数不会超过10,至少为1
009 var G = make([]IntHeap, 10)
010 
011 func main(){
012     var NumOfV, NumOfE int
013     //接受顶点数和边数
014     _, err := fmt.Scanf("%d %d\n",&NumOfV,&NumOfE)
015     if err != nil {
016         fmt.Println("error", err)
017     }
018     for i := 0; i<</SPAN>NumOfE; i++{//给顶点列表装入数据
019         var v1, v2 int
020         _, err = fmt.Scanf("%d %d\n",&v1,&v2)
021         if err != nil {
022             fmt.Println("error",err)
023         }
024         heap.Push(&G[v1],v2)
025         heap.Push(&G[v2],v1)
026     }
027     //************************************
028     //开始遍历
029     //*************************************
030     for i:= 0; i<</SPAN>NumOfV; i++ {
031         if !visited[i]{
032             fmt.Print("{ ")
033             dfs(i);
034             fmt.Print("}\n")
035         }
036     }
037     //重置visited数组
038     for i := range visited {
039         visited[i] = false
040     }
041     for i := 0; i<</SPAN>NumOfV; i++ {
042         if !visited[i]{
043             fmt.Print("{ ")
044             bfs(i)
045             fmt.Print("}\n")
046         }
047     }
048 }
049 //深度优先搜索(Depth First Search, DFS):
050 //访问下一个可见的未被访问的元素,
051 //如果所有的可见元素都被访问过,则返回上一个元素
052 func dfs(v int) (){
053     visited[v] = true
054     fmt.Printf("%d ",v)
055     for _,neibor := range G[v] { //遍历相邻节点
056         if !visited[neibor] {
057             dfs(neibor)
058         }
059     }
060 }
061 //广度优先搜索(Breadth First Search, BFS):
062 //类似层序遍历的思想,使用队列来操作,先把1放入队列,出队时,将1的所有邻接点放入队列
063 func bfs(v int) (){
064     var ls = list.New()
065     visited[v] = true
066     fmt.Printf("%d ", v)
067     ls.PushBack(v)
068     for ls.Len() != 0 {
069         ele := ls.Front()
070         ls.Remove(ele)
071         theV := ele.Value.(int)//theV.Value是接口类型,所以需要断言
072         
073         for _,neibor := range G[theV] {//遍历相邻节点
074             if !visited[neibor] {
075                 visited[neibor] = true
076                 fmt.Printf("%d ", neibor)
077                 ls.PushBack(neibor)
078             }
079         }
080     }
081 }
082 
083 //heap操作,最小堆
084 type IntHeap []int
085 
086 func (h IntHeap) Len() int           { return len(h) }
087 func (h IntHeap) Less(i, j int) bool { return h[i] <</SPAN> h[j] }
088 func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
089 
090 func (h *IntHeap) Push(x interface{}) {
091     // Push and Pop use pointer receivers because they modify the slice's length,
092     // not just its contents.
093     *h = append(*h, x.(int))
094 }
095 
096 func (h *IntHeap) Pop() interface{} {
097     old := *h
098     n := len(old)
099     x := old[n-1]
100     *h = old[0 : n-1]
101     return x
102 }


相关推荐

  • Linux 系统下 C 语言程序设计 Linux腺呜衣氖敢tfqc   目前Linux已经被广泛的使用,因此有必要简单介绍一下,在Linux系统下如何进行C  语言程序设计。首先介绍在Linux下如何编辑C语言源程序,接下来介绍如何编译C语言  源程序,  最好介绍如何调试与运行C语言源程序。  本节用一个
  • mycncart操作使用教程 - 语言设置 mycncart是多语言多货币网站,默认带有三种语言,分别是英文、简体中文、繁体中文。如果你想新增或者删除语言,操作路径为网站后台【系统设置】->【参数设置】->【语言设置】。注意新增语言时,请根据各个语言的国际编码来填写相关信
  • python中的  语言 解释器  标准库  build in (1)语言规定了一些基本的语法,当然可以包含一些基本的数据类型,但是要知道语言的核心是规则,也就是形成Python程序语句的一些规则,它的重点不是某些特定的对象或类型。他的重点是有关构成程序语句的关键字以及单词如何排列。(2)解释器是按照语
  • go 语言开发工具安装 Go语言是Google新推出的结合了动态语言和静态语言优势的一个新兴的语言。下面介绍一下如何在Mac系统下安装和使用这个语言。设置环境变量$GOROOTGO语言的根目录,通常是$HOME/go,当然也可以是任何其他目录。$GOOS和$GOA
  • 3.1 语言的设计 书名:《代码的未来》作者:松本行弘(YukihiroMatsumoto)译者:周自恒本试读章节摘自:『第3章编程语言的新潮流』接下来,我们从语言设计的角度,来比较一下Java、JavaScript、Ruby和Go这4种语言。这几种语言看起来
  • 第三章 语言的困境 大多数语言的消亡,不是以人的意志为转移的、也不是想保护就能保护的,它们在让人不知不觉中消亡——是历史的必然。这也是人类的一种悲哀。美国国家地理创建有声字典:记录世界濒危语言在人类发展史上,语言的纷乱是因为隔绝,其实各种语言诞生的过程应该是近
  • ♥_ .☆☆____<莫小春专属>._ C 语言入门教程 QQ:1326718615每晚与你们一起分享好看的情感日志和搞笑笑话?一、C语言的产生与发展C语言是1972年由美国的DennisRitchie设计发明的,并首次在UNIX操作系统的DECPDP-11计算机上使用。它由早期的编程语言BCPL
  • 如何设置Facebook 语言为中文?? 最近发现有人在玩FB但是很多人登录之后,显示的不是中文简体,然后也不知道要怎么改语言,因为看不懂!看不懂!看不懂!其实很简单,看图看图看图1.首先登录脸书之后点击主页,在整个界面的最右下角或者左下角是语言设置,点击下。2.点击语言设置,弹出
  • C 语言编译全过程 C语言编译全过程一.编译的概念:编译程序读取源程序(字符流),对之进行词法和语法的分析,将高级语言指令转换为功能等效的汇编代码,再由汇编程序转换为机器语言,并且按照操作系统对可执行文件格式的要求链接生成可执行程序。二.编译的完整过程:C源程
  • C 语言的前世今生 本篇是应《程序员》杂志约稿所写。原本要求是写篇谈C语言的短文。4000字以内。我刚列了个提纲就去了三千多字。-_-现放在这里,接管大师的攻讦斧正。勿转载。C语言的宿世此生C语言,从1970年月设计并实现之初,它就注定了带有强烈工程师文化的语
  • ARM  Architecture C 语言寻址解析—— 从U-Boot relocation所展开的探索(三) ARMArchitectureC语言寻址解析——从U-Bootrelocation所展开的探索(三)byLazyCatDesignwww.lazycatdesign.comARMArchitectureC语言PIC寻址方式解析(续)继续讨论
  • 第一章  语言 语言是人类之所以成为人类的标志,它伴随着人类的起源而出现,也将随着人类的消失而泯灭,没有语言,就没有人类。语言极大地促进人类的发展。人是自然的一部分,人作为地球生物进化的高级阶段,是大自然和人类自身演化的产物。开始,人是和其它动物一样生长于

你的评论

就没有什么想说的吗?

最新博客

关于我们 免责声明 移动版

©2017传客网    琼ICP备15003173号-2    

本站部分文章来源于互联网,版权归属于原作者。
本站所有转载文章言论不代表本站观点,如是侵犯了原作者的权利请发邮件联系站长(weishubao@126.com),我们收到后立即删除。
站内所有资源仅供学习与参考,请勿用于商业用途,否则产生的一切后果将由您自己承担!

X