| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1295324 | 123123123 | World Map (IOI25_worldmap) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int fix[245];
vector <vector <int> > build_mst(int N, const vector<vector<int> >& v)
{
vector <vector <int> > mst(N + 1);
vector <int> visited(N + 1, 0);
queue<int> q;
visited[1] = 1;
q.push(1);
while(!q.empty())
{
int u = q.front();
q.pop();
for(int j = 0; j < v[u].size(); j++)
{
if(!visited[v[u][j]])
{
visited[v[u][j]] = 1;
mst[u].push_back(v[u][j]);
mst[v[u][j]].push_back(u);
q.push(v[u][j]);
}
}
}
return mst;
}
void DFS(int u, int parent, const vector<vector<int> >& mst, vector<int>& order)
{
order.push_back(u);
for(int j = 0; j < mst[u].size(); j++)
{
if(mst[u][j] != parent) DFS(mst[u][j], u, mst, order);
}
}
int main()
{
int x, i, j, k, ind, N, M;
vector < vector <int> > v(N + 1);
vector <int> order, A, B;
cin >> N >> M;
for(i = 0; i < M; i++)
{
cin >> x;
A.push_back(x);
}
for(i = 0; i < M; i++)
{
cin >> x;
B.push_back(x);
}
if(M == 0)
{
vector <vector<int> > mymap(1, std::vector<int>(1, 1));
//return mymap;
}
for(i = 1; i <= N; i++)
{
v[i].clear();
}
order.clear();
for(i = 0; i < M; i++)
{
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
}
vector <vector <int> > mst = build_mst(N, v);
DFS(1, -1, mst, order);
vector <vector <int> > mymap(order.size() * 3, std::vector<int>(order.size() * 3, 0));
k = order.size() * 3;
cout << k << endl;
ind = 0;
for(i = 0; i < k; i++)
{
if(i % 3 == 0)
{
for(j = 0; j < k; j++)
{
mymap[i][j] = order[ind];
}
ind++;
}
}
for(i = 0; i < k; i++)
{
if(i % 3 == 2)
{
for(j = 0; j < k; j++)
{
mymap[i][j] = mymap[i - 2][j];
}
}
}
for(i = 0; i < k; i++)
{
if(i % 3 == 1)
{
for(j = 0; j < v[mymap[i - 1][0]].size() * 2; j++)
{
if(j % 2 == 0) mymap[i][j] = mymap[i - 1][0];
else mymap[i][j] = v[mymap[i - 1][0]][j / 2];
}
}
}
for(i = 0; i < k; i++)
{
for(j = 0; j < k; j++)
{
if(mymap[i][j] == 0) mymap[i][j] = mymap[i - 1][j];
}
}
for(i = 0; i < k; i++)
{
for(j = 0; j < k; j++)
{
cout << mymap[i][j] << " ";
}
cout << endl;
}
}