当前位置: 传客网 > PAT:05-1. List Components (25),Go语言解答

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

2016-10-07 作者:skyqqcloud

题目大概意思:给定一个有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寻址方式解析(续)继续讨论

  • 第一章  语言

    语言是人类之所以成为人类的标志,它伴随着人类的起源而出现,也将随着人类的消失而泯灭,没有语言,就没有人类。语言极大地促进人类的发展。人是自然的一部分,人作为地球生物进化的高级阶段,是大自然和人类自身演化的产物。开始,人是和其它动物一样生长于

  • ARM  Architecture C 语言寻址解析—— 从U-Boot relocation所展开的探索(一)

    ARMArchitectureC语言寻址解析——从U-Bootrelocation所展开的探索(一)byLazyCatDesignwww.lazycatdesign.com文章的名字有点长也有点拗口,但它却很好的表达了本文的主题和来历。这个

  • 上海图书公司图书专营店-古文观止(注音版)  李梦生 等著 语言文字 商城 正版

    上海图书公司图书专营店-古文观止(注音版)李梦生等著语言文字商城正版商品【古文观止(注音版)李梦生等著语言文字商城正版】是来自于天猫店铺上海图书公司图书专营店所经营的商品,其上海图书公司图书专营店主要经营的商品有:365作文启蒙,小米商城,

  • 课题研究计划《在小学英语教学中培养学生的 语言交际能力的研究》

    一、课题研究的目的意义:新的《英语课程标准》强调义务教育阶段英语课程的目的之一就是:使学生掌握一定的语言基本知识和基本技能,建立初步的语感,获得初步运用英语的能力,为真实交际打下基础”。新课程标准特别强调突出语言的实践性特征,目的就是培养学

  • C 语言的32个关键字

    程序中数据分两种:常量和变量。C语言中规定标识符只能由字母、数字、下划线三种字符组成。而且第一个字符只能是字母或下划线。注意:C语言是区分大小写的。ANSIC没有限定标识符的长度,编程时要根据不同版本的C编译环境制定标识符(主要是变量名)的

  • Go 语言初步(转载自云风的BLOG)

    Go语言初步(转载自云风的BLOG)原著连接:http://blog.codingnow.com/2010/11/go_prime.html这几天认真玩起了Go。所谓认真玩,就是拿Go写点程序,前后大约两千行吧。据说Go的最佳开发平台是Ma

  • Python、 R 语言、SAS、SPSS 优缺点比较

    Python、R语言、SAS、SPSS优缺点比较最近一直想入门数据分析的小伙伴问我,如果要入事数据分析一直来说要学那些语言呢?其实小编跟企业部门部门与侯选人接触下来,给我的感觉是对于这个初级的数据分析师来,一般前二年做差不多都是老大让你做的

  • MATLAB 与 C 语言的接口

    MATLAB到C语言程序的转换可以由两种途径完成,其一是MATLAB自己提供的C语言翻译程序mcc,另一种是原第3方公司MathTools开发的MATCOM。后者出现较早,功能远比MATLAB自己的翻译程序强大,所以MathTools公司已

  • 2.3第二章 声现象 第三节 声的利用 习题解答

    2.3第二章声现象第三节声的利用习题解答动手动脑学物理:第三节声的利用1、(1)利用声传递信息;(2)利用声能传递信息;(3)利用声能传递信息;(4)利用声能传递能量。2、3000m解析:声波在海水中的速度v=1500m/s,由于4s为一个

返回
顶部