P7069: 弱顶点

---

【题目描述】

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

图1：示例输入图中的弱顶点（带阴影）的图示。
【输入】
输入由多达100个图形组成。每个都以一个整数开始，1≤n≤20，表示图形中的顶点数。接下来是n行，每行上有n个整数，它们描述了图的n×n个邻接矩阵。顶点的编号从0到n-1。如果邻接矩阵在第r行第c列包含一个1（其中0≤r，c≤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

题目类型~

初级 难度1.6 图 

咻咻~

提交答案 状态 返回