【离散数学】SDUT OJ 补图

补图

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

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

Input

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

Output

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

Sample Input

Sample Output

#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;

}

巴特西