Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 1e3 + 10;
- vector<int> grafo[30*MAXN];
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- freopen("small-graph.in", "r", stdin);
- freopen("small-graph.out", "w", stdout);
- int N;
- cin >> N;
- vector<int> p(N+1);
- for (int i = 1; i <= N; i++) cin >> p[i];
- int arestas = 0;
- map<vector<int>, vector<int>> Marc;
- for (int i = 1; i <= N; i++)
- {
- int MaxP = -1;
- for (int j = i+1; j <= N; j++)
- {
- if (p[j] > p[i]) continue;
- if (MaxP > p[j]) continue;
- MaxP = p[j];
- arestas++;
- grafo[i].push_back(j);
- }
- sort(grafo[i].begin(), grafo[i].end());
- if (!grafo[i].empty()) Marc[grafo[i]].push_back(i);
- }
- int verti = N;
- for (auto [objs, ids] : Marc)
- {
- if (ids.size() == 1 || objs.size() == 1) continue;
- ++verti;
- for (auto i : ids)
- {
- arestas -= grafo[i].size();
- grafo[i].clear();
- arestas++;
- grafo[i].push_back(verti);
- }
- arestas += objs.size();
- grafo[verti] = objs;
- }
- assert(arestas <= 6*N);
- cout << verti << " " << arestas << '\n';
- for (int i = 1; i <= verti; i++) for (auto viz : grafo[i]) cout << i << " " << viz << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
