Need to find how many translators need for two persons to be able talking to each other.

Given values are

A : 1 2
B : 7 8
C : 4 5
D : 5 6 7
E : 6 7 8
F : 8 9

And the translators which we are looking for are as below

B > E Can translate directly, answer : 0
A > B Can't translate, answer : -1
C > F Need 2 translators C (5)> D(6)> E(8)> F(8), answer : 2
D > F need 1 translator D (6)> E(8)> F(8), answer : 1

And the code written is as below but I don't know how to traverse. Down is the graph picture which the nodes are basically A to F and matched them having same number.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

#define SIZE 1000
vector<char>* graph;
vector<int> v;
bool vis[SIZE]{ 0 };
int n = 9;

int Search(int start, char ch1, char ch2)
{
    int count = 0;
    queue<char> v1, v2;
    v1.push(ch1); v2.push(ch2);
    for (int i = 1; i < n; i  )
    {
        for (int j = 0; j < graph[i].size(); j  )
        {
            auto begin = graph[i].begin(), end = graph[i].end();
            auto iter1 = find(begin, end, v1.front()); 
            auto iter2 = find(begin, end, v2.front());
            auto lang = graph[i][j];
            if (iter1 != end &&
                lang != v1.front())
                v1.push(lang);

            if (iter2 != end &&
                lang != v2.front())
                v2.push(lang);

            
        }
    }
    fill(vis, vis   SIZE, false);
    return count;
}

int main()
{
    graph = new vector<char>[n 1];
    vector<string> people{ { "A 1 2" }, { "B 7 8" }, { "C 4 5" }, { "D 5 6 7" }, { "E 6 7 8" }, { "F 8 9" } };
    vector<string> pairs{ {"B E"}, {"A B"}, {"C F"}, {"D F"} };
    vector<int> res;
    for (int i = 1; i <= n; i  )
    {
        for (auto item : people)
        {
            item.erase(remove(item.begin(), item.end(), ' '), item.end());
            for (int j = 1; j < item.size(); j  )
            {
                int idx = item[j] - '0';
                if(i==idx)
                    graph[i].push_back(item[0]);
            }
        }
    }
    for (auto item : pairs)
    {
        item.erase(remove(item.begin(), item.end(), ' '), item.end());
        int count = Search(1, item[0], item[1]);
        cout << count << endl;
    }
    delete[] graph;
}

CodePudding user response：

I think your graph construction is wrong, it's not really a graph at all. You need to do some work to translate the input into a proper graph.

In your code you've created a mapping from language (1, 2, 3 etc) to translators (A, B, C etc) but really the problem is asking for a mapping from translators to translators (that speak the same language). So your graph should look like this

A -> 
B -> D E F
C -> D
D -> B C E
E -> B D F
F -> B E

Once you have a graph that connects translators I think you'll find it much easier to traverse. The languages themselves don't matter, all that matters is which translators speak a common language. That's what your graph should show.