CodeforcesRound#749(Div.1+Div.2,basedonTechnocup2022EliminationRound1)-B. Omkar and Heavenly Tree-题解

本文主要是介绍CodeforcesRound#749(Div.1+Div.2,basedonTechnocup2022EliminationRound1)-B. Omkar and Heavenly Tree-题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1) - B. Omkar and Heavenly Tree

传送门
Time Limit: 2 seconds
Memory Limit: 256 megabytes

Problem Description

Lord Omkar would like to have a tree with $n$ nodes $(3\le n\le 10^5)$ and has asked his disciples to construct the tree. However, Lord Omkar has created $m(1\le m<n)$ restrictions to ensure that the tree will be as heavenly as possible.

A tree with $n$ nodes is an connected undirected graph with $n$ nodes and $n-1$ edges. Note that for any two nodes, there is exactly one simple path between them, where a simple path is a path between two nodes that does not contain any node more than once.

Here is an example of a tree:

Input

Each test contains multiple test cases. The first line contains the number of test cases $t(1\le t\le 10^4)$. Description of the test cases follows.

The first line of each test case contains two integers, $n$ and $m(3\le n\le 10^5,1\le m<n)$, representing the size of the tree and the number of restrictions.

The i-th of the next m lines contains three integers $a_i,b_i,c_i$ ( $1\le a_i,b_i,c_i\le n,a,b,c$ are distinct), signifying that node $b_i$ cannot lie on the simple path between nodes $a_i$ and $c_i$.

It is guaranteed that the sum of $n$ across all test cases will not exceed $10^5$.

Output

For each test case, output $n-1$ lines representing the $n-1$ edges in the tree. On each line, output two integers $u$ and $v(1\le u,v\le n,u\ne v)$ signifying that there is an edge between nodes $u$ and $v$. Given edges have to form a tree that satisfies Omkar’s restrictions.

Sample Input

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

Sample Onput

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

Note

The output of the first sample case corresponds to the following tree:

For the first restriction, the simple path between $1$ and $3$ is $1$,$3$, which doesn’t contain $2$. The simple path between $3$ and $5$ is $3,5$, which doesn’t contain $4$. The simple path between $5$ and $7$ is $5,3,1,2,7$, which doesn’t contain $6$. The simple path between $6$ and $4$ is $6,7,2,1,3,4$, which doesn’t contain $5$. Thus, this tree meets all of the restrictions.

The output of the second sample case corresponds to the following tree:

---

题目大意

给你 $n$个节点的树和最多$n-1$个约束，其中每条约数包括三个数$a,b,c$，需要满足$b$不在$a,c$的最短路径上。

让你找到一种满足上述条件的树

解题思路

说白了就是 $b$ 不在 $a$ 和 $c$ 的中间。

既然给你了 $n-1$ 个约束条件，那么必有一点没当过 $b$，也就是说这个点可以在任何两点之间。

于是我们就可以以这个点为根，其他每个节点都连接到这个节点上面去。

也就是说假如 $点A$ 没有被限制在另外两点之间，那么就以 $A$ 为中心，其他点都连接到这个点上。

---

AC代码

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
bool visited[100010]; // visited[i]代表点i是否当过b
int main()
{int N;cin>>N;while(N--) {int n, m;cd(n), cd(m); // scanf n, mfor (int i = 1; i <= n; i++) {visited[i] = false; // 初始值这n个点都没当过b}for (int i = 0; i < m; i++) {int a,b,c;scanf("%d%d%d",&a,&b,&c);visited[b] = true; // b这个点当过b了}int notV = 0; // 没有当过b的点for (int i = 1; i <= n; i++) {if (!visited[i]) { // 找到了notV = i; // 赋值break; // 退出}}for (int i = 1; i <= n; i++) {if (i != notV) { // 除了这个点自己以外，所有点都连接到这个点上printf("%d %d\n", notV, i);}}}return 0;
}

原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/120835589

这篇关于CodeforcesRound#749(Div.1+Div.2,basedonTechnocup2022EliminationRound1)-B. Omkar and Heavenly Tree-题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---