2021安徽省大学生程序设计竞赛正式赛：G 连边问题_断开(a,b),(c,d)间的边,连接(a,c),(b,d)间的边

题目描述

给定一棵n个节点的树，如果树中存在边（a,b)(b,c)(c,d)，a,b,c,d互不相同，并且a和d之间没有边，那么可以连一条边(a,d)，求最多能连多少条边？

输入

第一行一个整数N，接下来N-1行，表示树的每一条边。

1 <= N <= 2×$10^5$

输出

输出一行，表示答案。

样例

提示

第 1 个样例，连边(1,4),(2,5),(1,6),(6,5)
第 2 个样例，连边(1,4),(1,6),(2,5),(3,6)
第 3 个样例，连边(1,8),(2,6),(2,7),(3,4),(3,5),(4,8),(5,8),(7,8)

解题思路

这道题目是有关图论的题目，关键在于如何找到要连接的边。
首先使用邻接矩阵来表示整个图，图的横坐标表示边的起点，图的纵坐标表示边的终点，将两个结点有边存在的表示为1，以此遍历有邻接边的结点，补全整个图，直到没有需要添加的边为止。添加的边的个数就是问题的解。

具体解法

首先输入一个整数表示结点的个数，然后一次输入边的起点和终点，利用邻接矩阵进行表示。如下图所示：

然后开始寻找要添加的边，直到需要添加的边数为0为止，循环结束，输出总需要添加的边数。最终的邻接矩阵为：

添加边数的方法：

1. 首先找到下标a标记（a,b)(b,c)(c,d)点a，即在邻接矩阵中为1的点，之后再找到这个边的终点，即下标b标记（a,b)(b,c)(c,d)中的点b，如果b不存在，则寻找下一个a点，如果b存在，则寻找与b相接的边的终点，即下标c标（a,b)(b,c)(c,d)中的点c，以此类推，直到找到d点。
2. 然后判断b点是否与d点相同，即是否找到的是一条回路，而不是要寻求的a、b、c、d均不相同的边。如果是回路的话继续寻找可能存在的d点，如果不相同，则就是要寻找的点，将邻接矩阵中的所在位置处的值标记为1，标记为存在边，同时将计数加一。
3. 最后判断增加的边数是否为0，即边数不能再增加，即循环退出的条件。

代码实现

#include <iostream>
#include<vector>
using namespace std;

int findfedge(vector<vector<int>> nlist, int bs,int N)
{
    int i = 0;
    while (i < N)
    {
        if (nlist[bs][i] == 1)
        {
            return i;
        }
        i++;

    }
    return -1;
}


int findnextedge(vector<vector<int>> nlist, int bs, int ne, int N)
{
    while (ne < N)
    {
        if (ne == N - 1)
        {
            return - 1;
        }
        ne++;
        if (nlist[bs][ne] == 1)
        {
            return ne;
        }

    }
    return - 1;
}


int islinkedge(vector<vector<int>> &numlist,int N)
{

    vector<vector<int>> nlist(numlist);

    int num = 0;
    int a = 0;
    while (a < N)
    {
        int b = findfedge(nlist, a, N);
        while (true)
        {
            if (b == -1)
            {
                break;
            }
            int c = findfedge(nlist, b, N);
            while (true)
            {
                if (c == a)
                {
                    c = findnextedge(nlist, b, c, N);
                }
                if (c == -1)
                {
                    break;
                }
                int d = findfedge(nlist, c, N);
                while (true)
                {
                    if (d == b)
                    {
                        d = findnextedge(nlist, c, d, N);
                    }
                    if (d == -1)
                    {
                        break;

                    }
                    if (nlist[a][d] == 0 && numlist[d][a] == 0)
                    {
                        numlist[a][d] = 1;
                        numlist[d][a] = 1;
                        num++;
                    }
                    d = findnextedge(nlist, c, d, N);

                }
                c = findnextedge(nlist, b, c, N);
            }
            b = findnextedge(nlist, a, b, N);
        }
        a++;
    }
    return num;
}

int main()
{
    int N;
    cin >> N;
    vector<vector<int>> numlist(N, vector<int>(N));
    for (int i = 0; i < N -1 ; i++)
    {

        int row, col;
        cin >> row >> col;

        numlist[row -1][col- 1] = 1;
        numlist[col -1][row - 1] = 1;
    }
   int sum = 0;
    while (true)
    {
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cout << numlist[i][j] << "\t";
            }
            cout << endl;
        }
        int num = islinkedge(numlist, N);
        if (num == 0)
        {
            break;
        }
        sum += num;
    }
    cout << sum << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

运行结果