fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. const int N = 1e5 + 5;
  7. int n, m;
  8. set<int> G[N];
  9. int vis[N];
  10. int deg(int u) {
  11.     return G[u].size();
  12. }
  13. struct Node {
  14.     int a, u, b;
  15. };
  16. int nxt[N];
  17. signed main() {
  18.     cin.tie(NULL)->sync_with_stdio(false);
  19.     if(ifstream("POLYGON.inp")) {
  20.         freopen("POLYGON.inp", "r", stdin);
  21.         freopen("POLYGON.out", "w", stdout);
  22.     }
  23.     cin >> n >> m;
  24.     if (n <= 3) return cout << "1 2 3", 0;
  25.     for (int i = 1; i <= n + m; i++) {
  26.         int u, v; cin >> u >> v;
  27.         if (u == v) continue;
  28.         G[u].insert(v);
  29.         G[v].insert(u);
  30.     }
  31.     vector<Node> ops;
  32.     int sz = n;
  33.     queue<int> Q;
  34.     for (int i = 1; i <= n; i++) if (deg(i) == 2) Q.push(i);
  35.     while(sz > 3) {
  36.         while (!Q.empty() && (vis[Q.front()] || deg(Q.front()) != 2)) Q.pop();
  37.         int u = Q.front(); Q.pop();
  38.         if (vis[u]) continue;
  39.         int a = *G[u].begin(), b = *G[u].rbegin();
  40.  
  41.         ops.push_back({a, u, b});
  42.         G[a].erase(u); G[b].erase(u);
  43.         G[u].clear();
  44.         vis[u] = 1; sz--;
  45.  
  46.         if (!G[a].count(b)) {
  47.             G[a].insert(b);
  48.             G[b].insert(a);
  49.         }
  50.         if (deg(a) == 2) Q.push(a);
  51.         if (deg(b) == 2) Q.push(b);
  52.     }
  53.     vector<int> rem;
  54.     rem.reserve(3);
  55.     for (int i = 1; i <= n; ++i) if (!vis[i]) rem.push_back(i);
  56.     for (int i = 0; i < 3; i++) {
  57.         nxt[rem[i]] = rem[(i + 1) % 3];
  58.     }
  59.  
  60.     for (int t = (int)ops.size() - 1; t >= 0; t--) {
  61.         int a = ops[t].a, u = ops[t].u, b = ops[t].b;
  62.         if (nxt[a] == b) {
  63.             nxt[a] = u;
  64.             nxt[u] = b;
  65.         }
  66.         else {
  67.             nxt[b] = u;
  68.             nxt[u] = a;
  69.         }
  70.     }
  71.     vector<int> ans;
  72.     for (int i = 0, cur = 1; i < n; i++) ans.push_back(cur), cur = nxt[cur];
  73.     if (ans[1] > ans.back()) {
  74.         reverse(ans.begin(), ans.end());
  75.         cout << "1 ";
  76.         for (int i: ans) if (i != 1) cout << i << " ";
  77.     }
  78.     else for (int i: ans) cout << i << " ";
  79.     return 0;
  80. }
  81. /*
  82. Vì đề kêu là cho các đường chéo của đa giác và các đường chéo không cách nhau
  83. nên luôn tồn tại >= 1 đỉnh chỉ có 2 cạnh 
  84.  
  85. Giả sử đó là đỉnh u
  86. và đỉnh u chỉ có 2 cạnh u - a và u-b
  87. Lưu lại cặp cạnh u - a và u - b
  88. Sau đó xóa đỉnh u và tạo cạnh mới a - b
  89.  
  90. Tiếp tục đa giác mới luôn tồn tại đỉnh u' chỉ có 2 cạnh
  91. Lặp lại bước trên đến khi nào đa giác mới chỉ còn 3 đỉnh thì ngưng lại
  92.  
  93. Giờ thì đảo ngược lại quá trình trên để xây lại đa giác ban đầu
  94. Đa giác hiện tại của ta giả sử có 3 cạnh X-Y, Y-Z, Z-X
  95. Nếu có cạnh X-u và u-Y thì thêm vào và xóa cạnh cũ X-Y, tạo ra đa giác mới X-u, u-Y, Y-Z, Z-X;
  96. Tương tự vậy đến hết là xong
  97.  
  98. vậy là được đa giác chỉ có các cạnh bao quanh (k có cạnh chéo)
  99. muốn có được thứ tự nhỏ nhất thì bắt đầu từ 1 và đi theo đỉnh hàng xóm nào có thứ tự nhỏ nhất là được
  100. */
Success #stdin #stdout 0.01s 8296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3
https://ideone.com/Tfy7GU
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!