编程介的小学生
2018-12-07 10:28
采纳率: 92.7%
浏览 396

最小生成树方面的一个问题,用C语言怎么解决的????

Problem Description
There is an undirected graph G with n vertices and m edges. Every time, you can select several edges and delete them. The edges selected must meet the following condition: let G′ be graph induced from these edges, then every connected component of G′ has at most one cycle. What is the minimum number of deletion needed in order to delete all the edges.

Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers n and m (1≤n≤2000,0≤m≤2000) -- the number of vertices and the number of edges.

For the next m lines, each line contains two integers ui and vi, which means there is an undirected edge between ui and vi (1≤ui,vi≤n,ui≠vi).

The sum of values of n in all test cases doesn't exceed 2⋅104. The sum of values of m in all test cases doesn't exceed 2⋅104.

Output
For each test case, output the minimum number of deletion needed.

Sample Input
3
4 2
1 2
1 3
4 5
1 2
1 3
1 4
2 3
2 4
4 4
1 2
2 3
3 4
4 1

Sample Output
1
2
1

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

2条回答 默认 最新

  • blownewbee 2019-03-28 23:45
    已采纳
    点赞 打赏 评论
  • weixin_44014185 2018-12-07 12:54

    #include
    #include
    #include

    #define MAXN 1000
    int map[MAXN][MAXN];
    int n;
    void Prim()
    {
    int i, j, minV, sum;
    int dis[n], pre[n];
    bool vist[n] = {0};
    vist[0] = 1;
    for (i = 0; i < n; i++)
    {
    dis[i] = map[0][i];
    pre[i] = 0;
    }
    sum = 0;
    for (i = 1; i < n; i++)
    {
    minV = -1;
    for (j = 0; j < n; j++)
    if (!vist[j] && (minV < 0 || dis[j] < dis[minV]))
    minV = j;
    vist[minV] = 1;
    sum += dis[minV];
    for (j = 0; j < n; j++)
    if (!vist[j] && dis[j] > map[minV][j])
    {
    dis[j] = map[minV][j];
    pre[j] = minV;
    }
    }
    printf("最小生成树的权为 = %d\n", sum);
    for (i = 0; i < n; i++)
    printf("边 %d - %d\n", i, pre[i]);
    }
    int main()
    {
    int i, j;
    printf("请输入结点数n:\n");
    scanf("%d", &n);
    printf("请输入邻接矩阵:\n");
    for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
    scanf("%d", &map[i][j]);
    prim();
    return 0;
    }
    //用prim写的,输入是邻接矩阵

    点赞 打赏 评论

相关推荐 更多相似问题