Find Strong Vertices in a Directed Graph - C++ Implementation

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"≠"v") exists if "au"-"av"≥"bu"-"bv".

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 graph has only one strong vertex with number 4 Input The first line contains an integer "t" (1≤"t"≤104) — the number of test cases.

The first line of each test case contains an integer "n" (2≤"n"≤2⋅105) — the length of "a" and "b".

The second line of each test case contains "n" integers "a1,a2…an" (−109≤"ai"≤109) — the array "a".

The third line of each test case contains "n" integers "b1,b2…bn" (−109≤"bi"≤109) — the array "b".

It is guaranteed that the sum of "n" for all test cases does not exceed 2⋅105.

Output For 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.c++代码内容：Here is a possible C++ implementation to solve the problem:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> getStrongVertices(vector<int>& a, vector<int>& b) {
    int n = a.size();
    vector<int> strongVertices;
    
    // Find the maximum value of a[i] - b[i]
    int maxDiff = a[0] - b[0];
    for (int i = 1; i < n; i++) {
        int diff = a[i] - b[i];
        maxDiff = max(maxDiff, diff);
    }
    
    // Find the vertices that have a[i] - b[i] >= maxDiff for all i
    for (int i = 0; i < n; i++) {
        if (a[i] - b[i] >= maxDiff) {
            strongVertices.push_back(i + 1);
        }
    }
    
    return strongVertices;
}

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        vector<int> a(n), b(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> b[i];
        }
        
        vector<int> strongVertices = getStrongVertices(a, b);
        
        cout << strongVertices.size() << endl;
        for (int i = 0; i < strongVertices.size(); i++) {
            cout << strongVertices[i] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

This implementation uses a function getStrongVertices to compute the strong vertices for a given test case. It iterates through the arrays a and b to find the maximum difference maxDiff between a[i] - b[i]. Then, it iterates again to find the vertices that have a[i] - b[i] >= maxDiff and adds them to the strongVertices vector. Finally, in the main function, the input is read and the getStrongVertices function is called for each test case, and the result is printed.