shunfurh
编程介的小学生
2019-01-07 12:58
采纳率: 92.7%
浏览 560

数据结构C语言计算,要用数组的顺序表的插入删除

Problem Description
Betty owns a lot of ponds, some of them are connected with other ponds by pipes, and there will not be more than one pipe between two ponds. Each pond has a value v.

Now Betty wants to remove some ponds because she does not have enough money. But each time when she removes a pond, she can only remove the ponds which are connected with less than two ponds, or the pond will explode.

Note that Betty should keep removing ponds until no more ponds can be removed. After that, please help her calculate the sum of the value for each connected component consisting of a odd number of ponds

Input
The first line of input will contain a number T(1≤T≤30) which is the number of test cases.

For each test case, the first line contains two number separated by a blank. One is the number p(1≤p≤104) which represents the number of ponds she owns, and the other is the number m(1≤m≤105) which represents the number of pipes.

The next line contains p numbers v1,...,vp, where vi(1≤vi≤108) indicating the value of pond i.

Each of the last m lines contain two numbers a and b, which indicates that pond a and pond b are connected by a pipe.

Output
For each test case, output the sum of the value of all connected components consisting of odd number of ponds after removing all the ponds connected with less than two pipes.

Sample Input
1
7 7
1 2 3 4 5 6 7
1 4
1 5
4 5
2 3
2 6
3 6
2 7

Sample Output
21

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • caozhy
    已采纳
    点赞 评论
  • weixin_44432927
    weixin_44432927 2019-01-07 13:16

    顺序表的基本功能C语言实现: (基于静态数组)
    1. 初始化
    2. 尾插
    3. 尾删
    4. 头插
    5. 头删
    6. 读任意位置元素
    7. 修改任意位置元素
    8. 查找指定元素值的下标
    9. 在任意位置插入元素
    10.删除顺序表中指定的值, 如果存在重复元素, 只删除第一个
    11.删除顺序表中所有的指定的值, 另外要实现一个时间复杂度为 O(N) 的优化版本
    12.获取顺序表元素个数
    13.判定顺序表是否为空

    14.冒泡排序

    点赞 评论
  • qq_43060532
    qq_43060532 2019-01-07 13:38

    C语言实现
    初始化
    尾插 尾删
    头插
    头删
    读任意位置元素 . 修改任意位置元素
    查找指定元素值的下标
    在任意位置插入元素
    .删除顺序表中指定的值, 如果存在重复元素, 只删除第一个
    删除顺序表中所有的指定的值, 另外要实现一个时间复杂度为 O(N) 的优化版本
    获取顺序表元素个数 判定顺序表是否为空

    点赞 评论

相关推荐