310597: CF1857D. Strong Vertices
Description
Given two arrays $a$ and $b$, both of length $n$. Elements of both arrays indexed from $1$ to $n$. You are constructing a directed graph, where edge from $u$ to $v$ ($u\neq v$) exists if $a_u-a_v \ge b_u-b_v$.
A vertex $V$ is called strong if there exists a path from $V$ to all other vertices.
A path in a directed graph is a chain of several vertices, connected by edges, such that moving from the vertex $u$, along the directions of the edges, the vertex $v$ can be reached.
Your task is to find all strong vertices.
For example, if $a=[3,1,2,4]$ and $b=[4,3,2,1]$, the graph will look like this:
The first line contains an integer $t$ ($1\le t\le 10^4$) — the number of test cases.
The first line of each test case contains an integer $n$ ($2 \le n \le 2\cdot 10^5$) — the length of $a$ and $b$.
The second line of each test case contains $n$ integers $a_1,a_2 \dots a_n$ ($-10^9 \le a_i \le 10^9$) — the array $a$.
The third line of each test case contains $n$ integers $b_1,b_2 \dots b_n$ ($-10^9 \le b_i \le 10^9$) — the array $b$.
It is guaranteed that the sum of $n$ for all test cases does not exceed $2\cdot 10^5$.
OutputFor each test case, output two lines: in the first line, output the number of strong vertices, and in the second line, output all strong vertices in ascending order.
ExampleInput5 4 3 1 2 4 4 3 2 1 5 1 2 4 1 2 5 2 3 3 1 2 1 2 2 1 3 0 2 1 1 3 2 3 5 7 4 -2 -3 -6Output
1 4 2 3 5 1 2 3 1 2 3 2 2 3Note
The first sample is covered in the problem statement.
For the second sample, the graph looks like this:
In the third sample, the vertices are connected by a single directed edge from vertex $2$ to vertex $1$, so the only strong vertex is $2$.
In the fourth sample, all vertices are connected to each other by bidirectional edges, so there is a path from every vertex to any other vertex.
Output
输入数据格式:第一行包含一个整数t(1≤t≤10^4),表示测试用例的数量。每个测试用例包含三行,第一行是一个整数n(2≤n≤2×10^5),表示数组a和b的长度。第二行包含n个整数a_1, a_2, ..., a_n(-10^9≤a_i≤10^9),表示数组a。第三行包含n个整数b_1, b_2, ..., b_n(-10^9≤b_i≤10^9),表示数组b。所有测试用例的n之和不超过2×10^5。
输出数据格式:对于每个测试用例,输出两行。第一行输出强节点的数量,第二行按升序输出所有强节点的编号。
示例:
输入:
```
5
4
3 1 2 4
4 3 2 1
5
1 2 4 1 2
5 2 3 3 1
2
1 2
2 1
3
0 2 1
1 3 2
3
5 7 4
-2 -3 -6
```
输出:
```
1
4
2
3 5
1
2
3
1 2 3
2
2 3
```题目大意:给定两个长度为n的数组a和b,元素下标从1到n。根据条件a_u - a_v ≥ b_u - b_v构建一个有向图,图中每个节点u到节点v(u ≠ v)存在一条边当且仅当该条件成立。如果一个节点V到图中所有其他节点都存在路径,则称该节点为强节点。要求找出所有的强节点。 输入数据格式:第一行包含一个整数t(1≤t≤10^4),表示测试用例的数量。每个测试用例包含三行,第一行是一个整数n(2≤n≤2×10^5),表示数组a和b的长度。第二行包含n个整数a_1, a_2, ..., a_n(-10^9≤a_i≤10^9),表示数组a。第三行包含n个整数b_1, b_2, ..., b_n(-10^9≤b_i≤10^9),表示数组b。所有测试用例的n之和不超过2×10^5。 输出数据格式:对于每个测试用例,输出两行。第一行输出强节点的数量,第二行按升序输出所有强节点的编号。 示例: 输入: ``` 5 4 3 1 2 4 4 3 2 1 5 1 2 4 1 2 5 2 3 3 1 2 1 2 2 1 3 0 2 1 1 3 2 3 5 7 4 -2 -3 -6 ``` 输出: ``` 1 4 2 3 5 1 2 3 1 2 3 2 2 3 ```