问题7069--弱顶点

7069: 弱顶点

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

【题目描述】

工程师喜欢使用三角形。这可能与三角形如何提供大量结构强度有关。我们可以用无向图描述一些设计的物理结构。我们会说顶点是三角形的一部分,如果我有两个不同的顶点jk,使得jk是彼此的邻居。对于这个问题,在图中找到弱顶点——那些不是任何三角形一部分的顶点。


1:示例输入图中的弱顶点(带阴影)的图示。

输入

输入由多达100个图形组成。每个都以一个整数开始,1≤n≤20,表示图形中的顶点数。接下来是n行,每行上有n个整数,它们描述了图的n×n个邻接矩阵。顶点的编号从0n-1。如果邻接矩阵在第r行第c列包含一个1(其中0≤rc≤n-1),则意味着从顶点到顶点存在一条边。由于图是无向的,邻接矩阵是对称的。输入的结束由n的值-1标记。

输出

对于每个图,生成一条线,列出从最小到最大排序的弱顶点。

样本输入1】

9

0 1 1 1 0 0 0 0 0

1 0 0 0 0 0 1 0 0

1 0 0 1 0 1 0 0 0

1 0 1 0 0 1 1 0 0

0 0 0 0 0 0 1 1 0

0 0 1 1 0 0 0 0 0

0 1 0 1 1 0 0 1 0

0 0 0 0 1 0 1 0 1

0 0 0 0 0 0 0 1 0

1

0

-1

样本输出1】

1 8

0

样例输入 复制


样例输出 复制


来源/分类