CF-22C普及+/提高
割点图
⏱ 1.0s💾 256MB
📋 题目描述
请你构造一张包含 个顶点( 编号从 到 ), 条边的无向连通图,要求指定的顶点 为图的割点。
📥 输入格式
仅有一行,包含三个整数 ( , ,)。
📤 输出格式
如果无法构造出题目要求的无向图,则输出 ,否则输出 行,每行包含两个正整数 和 ( ),两数间用一个空格分隔,表示顶点 和顶点 之间有一条无向边连接。如果答案不唯一,可以输出任意一种符合要求的方案。
📝 样例 1
输入
5 6 3
输出
1 2 2 3 3 4 4 5 1 3 3 5
📝 样例 2
输入
6 100 1
输出
-1
📚 来源
Problem:CF-22C
💡 题目讲解
1
理解题意
给你三个数:(顶点数)、(边数)、(指定的顶点编号)。
你要构造一张无向连通图,要求顶点 是图的割点(articulation point)。
💡 什么叫"割点"? 把割点和它连的边删掉后,图会裂成两块或多块互不连通的部分。
例如下面这张图——顶点 3 就是割点。
造不出来(边太多或太少)就输出 -1。具体多少算多、多少算少,咱们后面慢慢算。
绿色圆 = 普通顶点,红色圆 = 割点,橙线 = 连割点,绿线 = 组内互连
1 / 5