补图

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

题目给出一个无向图,求该无向图关于完全图的相对补图,并求该补图的最大度和最小度。方便起见,用邻接矩阵表示该无向图。无向图的节点数不少于2并且不超过500.

Input

多组输入,每组输入第一行是无向图中节点的数量即邻接矩阵的行列数n。接下来n行n列为该图的邻接矩阵。

Output

每组数据,首先输出n行n列表示补图的邻接矩阵。接下来一行两个用空格分隔的整数,分别代表补图的最大度和最小度。

Sample Input

4
0 0 1 1
0 0 0 1
1 0 0 0
1 1 0 0

Sample Output

0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
2 1
#include <stdio.h>
#include <stdlib.h>
#define MA 550 int main()
{
int n;
int G[MA][MA];
int i, j;
int max, min;
int deg;
while(~scanf("%d", &n))
{
max = 0;
min = MA;
for(i=0; i<n; i++)
{
deg = 0; //初始化每个节点的度数
for(j=0; j<n; j++)
{
scanf("%d", &G[i][j]);
if(i != j) //输入直接求补图该节点的边,减小时间复杂度
{
if(G[i][j] == 1)
{
G[i][j] = 0;
}
else
{
G[i][j] = 1;
}
}
if(G[i][j] == 1)
{
deg++; //计算度数
}
}
if(deg > max)
{
max = deg;
}
if(deg < min)
{
min = deg;
}
} for(i=0; i<n; i++)
{
for(j=0; j<n-1; j++)
{
printf("%d ", G[i][j]);
}
printf("%d\n", G[i][j]);
}
printf("%d %d\n", max, min);
}
return 0;
}
05-11 20:06