#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];
}
}
void fill_map_with_node2(int node, int row, vector<vector<int>>& adj, vector<vector<int>>& map){
for(int j = 0; j < map[row].size(); j ++){
map[row][j] = node;
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
if(M == 0){
vector<vector<int>> res(3, vector<int>(3, 1));
return res;
}
vector<vector<int>> res(240, vector<int>(240, 0));
for(int i = 0; i < res[0].size(); i ++){
res[0][i] = 0;
}
int start = -1;
vector<vector<int>> adj(N+1, vector<int>());
for(int i = 0; i < M; i ++){
start = A[i];
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
unordered_set<int> global_unvisited;
for(int i = 1; i <= N; i ++) global_unvisited.insert(i); // Node 1 will be the first node we visit.
global_unvisited.erase(start);
int cur_node = start;
int row = 3;
fill_map_with_node(start, 0, adj, res);
set<int> seen;
seen.insert(start);
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);
// Explored the entire graph available (and this is only a subset of nodes)
if(!global_unvisited.count(path.back())){
break;
}
for(int i = 1; i < path.size(); i ++){
if(!seen.count(path[i])){
fill_map_with_node(path[i], row, adj, res);
row += 3;
seen.insert(path[i]);
} else {
fill_map_with_node2(path[i], row, adj, res);
row += 1;
}
//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 = 0; 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
5 2
2 3
3 4
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
*/
