Какой самый оптимальный способ печати пути от корня до каждого листа дерева? - PullRequest
Новая
       44

Какой самый оптимальный способ печати пути от корня до каждого листа дерева?

0 голосов
/ 12 апреля 2019

Введите

T- тестовые случаи

N-количество узлов

N-1 строк следует

x y - между x и y есть грань 

1
5
1 2
2 5
1 3
3 4

выход 

Path 1 3 4
Path 1 2 5

подход

Сначала я делаю BFS на дереве и сохраняю все родительские значения для каждого Затем для каждого конечного узла я возвращаюсь к корню, используя родительские значения. Я помещаю их в вектор пути и печатаю вектор пути. Однако я думаю, что решение очень неэффективно по времени. Ты можешь предложить лучший способ?

Мой код - он получает TLE 

void bfs(vector<int> adj[], int start, int n, int val[], int mod[]) {

    int parent[n + 1];
    bool visited[n + 1];
    memset(visited, false, sizeof(visited));
    for (int i = 1; i <= n; ++i)
    {
        /* code */
        parent[i] = -1;
    }



    queue<int> q;
    q.push(start);
    parent[start] = -1;
    visited[start] = true;
    while (!q.empty()) {
        int x;
        x = q.front();
        q.pop();

        for (auto u : adj[x]) {
            if (!visited[u]) {
                q.push(u);
                parent[u] = x;
                visited[u] = true;
            }

        }



    }

    vector<int> leaf;
    //check if a leaf node
    for (int i = 1; i <= n; i++) {
        if (adj[i].size() == 1)
            leaf.pb(i);

    }


    for (auto x : leaf) {
        vector<int> path;
        for (int v = x; v != -1; v = parent[v])
            path.push_back(val[v]);
        cout<<"Path"<<" ";
        for(auto x:path)
           cout<<x<<" ";
        cout<<endl;

    }



}

int main(){
int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        std::vector<int> adj[n + 1];
        int edges = n - 1;
        while (edges--) {
            int x, y;
            cin >> x >> y;
            adj[x].pb(y);
            adj[y].pb(x);
        }

        int val[n + 1];
        int mod[n + 1];

        for (int i = 1; i <= n; i++) {
            /* code */
            cin >> val[i];
        }
        for (int i = 1; i <= n; i++) {
            /* code */
            cin >> mod[i];
        }



        bfs(adj, 1, n, val, mod);
        cout<<endl;
      return 0;
     }
...