#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; // } vector<int> bfs(int start, vector<vector<int>>& adj, unordered_set<int>& global_unvisited){ queue<int> q; q.push(start); int cur_node = start; vector<int> parent(adj.size() + 1, -1); vector<int> visited(adj.size() + 1, 0); visited[start] = 1; int result_node; while(!q.empty()){ cur_node = q.front(); q.pop(); if(global_unvisited.count(cur_node)){ result_node = cur_node; break; } for(int next : adj[cur_node]){ if(!visited[next]){ visited[next] = 1; parent[next] = cur_node; q.push(next); } } } vector<int> path; while(cur_node != start){ path.push_back(cur_node); cur_node = parent[cur_node]; } path.push_back(start); reverse(path.begin(), path.end()); return path; } void fill_map_with_node(int node, int row, vector<vector<int>>& adj, vector<vector<int>>& map){ for(int i = row; i < row + 3; i ++){ for(int j = 0; j < map[row].size(); j ++){ map[i][j] = node; } } for(int j = 0; j < adj[node].size(); j ++){ map[row+1][j*2+1] = adj[node][j]; } } std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) { vector<vector<int>> res(240, vector<int>(240, 0)); for(int i = 0; i < res[0].size(); i ++){ res[0][i] = 0; } 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]); } unordered_set<int> global_unvisited; for(int i = 2; i <= N; i ++) global_unvisited.insert(i); // Node 1 will be the first node we visit. int cur_node = 1; int row = 3; fill_map_with_node(1, 0, adj, res); while(!global_unvisited.empty()){ /* Let's say we're at position u. Run BFS, which will tell us the path to the closest node inside global_unvisited. */ vector<int> path = bfs(cur_node, adj, global_unvisited); for(int i = 1; i < path.size(); i ++){ fill_map_with_node(path[i], row, adj, res); row += 3; //cout << path[i] << " "; } //cout << "\n"; int final_node = path.back(); cur_node = final_node; global_unvisited.erase(cur_node); } int necessary_size = 0; for(int i = 1; i < res.size(); i ++){ //for(int j = 0; j < res[i].size(); j ++){ if(res[i][0] == 0){ necessary_size = i; break; //res[i][j] = res[i-1][j]; } //} } vector<vector<int>> smaller_map(necessary_size, vector<int>(necessary_size, 0)); for(int i = 0; i < smaller_map.size(); i ++){ for(int j = 0; j < smaller_map.size(); j ++){ smaller_map[i][j] = res[i][j]; } } return smaller_map; } /* 1 6 5 1 2 2 3 2 4 2 5 3 6 1 : 2 2 : 1, 3, 4, 5 3 : 2, 6 4 : 2 5 : 2 6 : 3 1111111 1213161 1111111 2222222 2123252 2222222 3 4 | 1 - 2 - 3 - 6 | 5 1 - 2 - 3 | 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 */