P11433 [COCI 2024/2025 #2] 三角 / Trokuti

题目背景

译自 COCI 2024/2025 #2 T5。$\texttt{4s,0.5G}$。满分为 $120$。

题目描述

给定一张 $6n$ 个节点 $m$ 条边的无向图。保证这张图可以被划分成 $2n$ 个 $K_3$（大小为 $3$ 的完全图）。

求出这张图中的 $n$ 个 $K_3$，不能有重复顶点。

输入格式

本题单个测试点内有多组测试数据。

第一行，一个正整数 $T$，表示测试数据组数。

接下来描述 $T$ 组数据：

第一行，两个整数 $n,m$。

接下来 $m$ 行，每行两个正整数 $u,v$，表示图中的一条无向边。

输出格式

每组数据输出 $n$ 行，每行三个整数，表示 $K_3$ 的三个顶点。

输入输出样例 #1

输入 #1

1
1 6
1 2
2 3
1 3
4 5
4 6
5 6

输出 #1

1 2 3

输入输出样例 #2

输入 #2

1
3 26
4 7
4 9
7 9
4 5
4 8
5 8
4 12
4 18
12 18
3 7
3 9
15 5
15 8
6 13
6 1
13 1
6 14
6 17
14 17
6 2
6 10
2 10
16 13
16 1
11 14
11 17

输出 #2

1 6 13
3 7 9
4 5 8

说明/提示

对于 $100\%$ 的数据，保证：

• $1\le T\le 100$；
• $1\le n,\sum n\le 300$；
• $0\le m\le 10^6$；
• $1\le u,v\le 6n$。

子任务编号	$n,\sum n$	特殊性质	得分
$1$	$\le 300$	A	$13$
$2$	$=3$	B	$18$
$3$	$=6$
$4$	$\le 300$		$71$

• 特殊性质 A：$m=6n$。
• 特殊性质 B：$T=1$。

#5702. 「COCI 2024/2025 #2」Trokuti

标签: 传统 | 时间限制: 4000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #2 T5「Trokuti」

给定一个具有 $6 \cdot N$ 个顶点和 $M$ 条边的无向图。该图的一个额外属性是它可以被划分为 $2 \cdot N$ 个不相交的三角形。

在图中找到 $N$ 个不相交的三角形。

输入格式

第一行包含一个正整数 $T$ $(1 \leq T \leq 100)$，表示测试用例的数量。

接下来是 $T$ 个测试用例。

每个测试用例的第一行包含自然数 $N$ 和 $M$ $(1 \leq N \leq 300, 0 \leq M \leq 10^{6})$。

在接下来的 $M$ 行中，每行有两个正整数 $x$ 和 $y$ $(1 \leq x, y \leq 6 \cdot N)$，表示顶点 $x$ 和 $y$ 之间存在一条边。

所有测试用例中 $N$ 的值之和不会超过 $300$。

输出格式

对于每个测试用例，输出 $N$ 行，每行包含三个正整数 $a, b, c$ $(1 \leq a, b, c \leq 6 \cdot N)$，表示顶点 $a, b$ 和 $c$ 构成一个三角形。

样例 1

输入

1
1 6
1 2
2 3
1 3
4 5
4 6
5 6

输出

1 2 3

样例 2

输入

1
3 26
4 7
4 9
7 9
4 5
4 8
5 8
4 12
4 18
12 18
3 7
3 9
15 5
15 8
6 13
6 1
13 1
6 14
6 17
14 17
6 2
6 10
2 10
16 13
16 1
11 14
11 17

输出

1 6 13
3 7 9
4 5 8

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$13$	$M=6 \cdot N$
$2$	$18$	$N=3, T=1$
$3$	$18$	$N=6, T=1$
$4$	$71$	无附加限制