SWUSTOJ #1060 无向图的最大度计算

SWUSTOJ #1060 无向图的最大度计算

  • 题目
    • 输入
    • 输出
    • 样例输入
    • 样例输出
  • 源代码

题目

假设无向图G采用邻接矩阵存储，求出图G最大度值并输出顶点的编号（有多个结果的都要输出）。

输入

第一行为一个整数n，表示顶点的个数（顶点编号为0到n-1）。接下来是为一个n*n大小的整数矩阵，表示图的邻接关系。数字为0表示不邻接，1表示邻接。

输出

图G中度的最大值以及顶点编号。第一行表示最大度值，第二行表示所有顶点的编号。

样例输入

5
0 1 0 1 1
1 0 1 1 1
0 1 0 1 1
1 1 1 0 1
1 1 1 1 0

样例输出

4
134

源代码

#include <iostream>using namespace std;int main()
{int count[100];int n;cin >> n;int arr[1000][1000];for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){cin >> arr[i][j];if (arr[i][j] == 1)count[i]++;}}int max = 0;int arr1[100];int j = 0;for (int i = 0; i < n; i++){if (count[i]>max)max = count[i];}for (int i = 0; i < n; i++){if (count[i] == max){arr1[j] = i;j++;}}cout << max << endl;for (int i = 0; i < j; i++){cout << arr1[i];}return 0;
}

SWUSTOJ #1060 无向图的最大度计算

SWUSTOJ #1060 无向图的最大度计算

  • 题目
    • 输入
    • 输出
    • 样例输入
    • 样例输出
  • 源代码

题目

假设无向图G采用邻接矩阵存储，求出图G最大度值并输出顶点的编号（有多个结果的都要输出）。

输入

第一行为一个整数n，表示顶点的个数（顶点编号为0到n-1）。接下来是为一个n*n大小的整数矩阵，表示图的邻接关系。数字为0表示不邻接，1表示邻接。

输出

图G中度的最大值以及顶点编号。第一行表示最大度值，第二行表示所有顶点的编号。

样例输入

5
0 1 0 1 1
1 0 1 1 1
0 1 0 1 1
1 1 1 0 1
1 1 1 1 0

样例输出

4
134

源代码

#include <iostream>using namespace std;int main()
{int count[100];int n;cin >> n;int arr[1000][1000];for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){cin >> arr[i][j];if (arr[i][j] == 1)count[i]++;}}int max = 0;int arr1[100];int j = 0;for (int i = 0; i < n; i++){if (count[i]>max)max = count[i];}for (int i = 0; i < n; i++){if (count[i] == max){arr1[j] = i;j++;}}cout << max << endl;for (int i = 0; i < j; i++){cout << arr1[i];}return 0;
}