#include "worldmap.h" using namespace std; #include <bits/stdc++.h> int dfs(int u, int row, int col, vector<int>& node_sizes, vector<vector<int>>& adj, vector<vector<int>>& res){ /* For each node, we wish to determine the size of each of its children */ if(node_sizes[u] != 0) return 0; // skip visited nodes node_sizes[u] = 1; // Base case: leaf node if(u != 1 && adj[u].size() == 1){ //node_sizes[u] = 1; return 1; } // Recursion case int pos = col + 1; res[row][col] = u; for(int v : adj[u]){ int width_v = dfs(v, row+1, pos, node_sizes, adj, res); if(width_v){ for(int j = pos; j < pos + width_v; j ++){ res[row][j] = v; } res[row][pos+width_v] = u; pos += width_v + 1; } } //node_sizes[u] = pos-col; return pos - col; } std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) { // std::vector<std::vector<int>> ans(2 * N, std::vector<int>(2 * N, 1)); // if (M > 0) { // ans[0][0] = A[0]; // ans[0][1] = B[0]; // } vector<vector<int>> res(240, vector<int>(240, 0)); for(int i = 0; i < res[0].size(); i ++){ res[0][i] = 1; } vector<vector<int>> adj(N+1, vector<int>()); for(int i = 0; i < M; i ++){ adj[A[i]].push_back(B[i]); adj[B[i]].push_back(A[i]); } vector<int> node_sizes(N+1, 0); dfs(1, 1, 0, node_sizes, adj, res); for(int i = 1; i < res.size(); i ++){ for(int j = 0; j < res[i].size(); j ++){ if(res[i][j] == 0){ res[i][j] = res[i-1][j]; } } } return res; } /* 1 6 5 1 2 2 3 3 4 4 5 5 6 1 3 2 1 2 1 3 1 9 8 1 2 1 3 1 4 4 5 4 6 4 7 5 8 5 9 Parents of leaf nodes require 2x+1 horizontal cells 1 1 1 1 1 1 1 1 1 1 1 1 2 1 3 1 4 4 4 4 4 1 0 0 0 0 0 4 5 4 6 4 0 For exmaple, node 1 requires 7 cells. But let's say, 4 is the parent of 5 6 4 4 4 4 4 4 5 4 6 4 If a node x requires N cells, add N+1 to the number of cells the parent requires. Finally, add an extra cell to the parent */