SHARE
TWEET

Prufer Code from Tree

WadeRollins2710 Nov 8th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Trần Việt Anh - 8/11/2019 - 11:15PM
  2. #include<iostream>
  3. #include<map>
  4. #include<vector>
  5. #include <queue>
  6. #include <set>
  7.  
  8. using namespace std;
  9.  
  10. int main() {
  11.     int lineCount;
  12.     priority_queue<int> vertex;
  13.     map<int, vector<int> > tree;
  14.     map<int, int> vertexCount;
  15.     set<int> nodeSet;
  16.  
  17.     cin >> lineCount;
  18.     for (int i = 0; i < lineCount; i++) {
  19.         int x, y; cin >> x >> y;
  20.         nodeSet.insert(x); nodeSet.insert(y);
  21.  
  22.         map<int, int>::iterator it = vertexCount.find(x);
  23.        
  24.         if (it == vertexCount.end()) {
  25.             //cout << "new " << x << endl;
  26.             vertex.push(-x);
  27.             vertexCount[x] = 1;
  28.             vector<int> values(1, y);
  29.             tree[x] = values;
  30.         }
  31.         else {
  32.             vertexCount[x] += 1;
  33.             tree[x].push_back(y);
  34.         }
  35.  
  36.         it = vertexCount.find(y);
  37.         if (it == vertexCount.end()) {
  38.             //cout << "new " << y << endl;
  39.             vertex.push(-y);
  40.             vertexCount[y] = 1;
  41.             vector<int> values(1, x);
  42.             tree[y] = values;
  43.         }
  44.         else {
  45.             vertexCount[y] += 1;
  46.             tree[y].push_back(x);
  47.         }
  48.     }
  49.  
  50.     int n = nodeSet.size();
  51.     vector<int> sortedVertex(0);
  52.     while (vertex.size() != 0) {
  53.         sortedVertex.push_back(-vertex.top());
  54.         vertex.pop();
  55.     }
  56.  
  57.     // for (int i = 0; i < sortedVertex.size(); i++) {
  58.     //  cout << sortedVertex[i] << " ";
  59.     // }
  60.     // cout << endl;
  61.  
  62.     // for (int i = 0; i < sortedVertex.size(); i++) {
  63.     //  cout << "Node Value: " << sortedVertex[i] << endl;
  64.     //  cout << "Count: " << vertexCount[sortedVertex[i]] << endl;
  65.     //  cout << "Size: " << tree[sortedVertex[i]].size() << endl;
  66.     //  for (int j = 0; j < tree[sortedVertex[i]].size(); j++)
  67.     //      cout << tree[sortedVertex[i]][j] << "-";
  68.     //  cout << endl;
  69.     // }
  70.  
  71.     bool checked[sortedVertex.size()];
  72.     for (int i = 0; i < sortedVertex.size(); i++)
  73.         checked[i] = false;
  74.    
  75.     for (int i = 0; i < n - 2; i++) {
  76.         for (int nodeIndex = 0; nodeIndex < sortedVertex.size(); nodeIndex++) {
  77.             if (!checked[nodeIndex]) {
  78.                 checked[nodeIndex] = true;
  79.                 bool valid = true;
  80.                 for (int j = 0; j < tree[sortedVertex[nodeIndex]].size(); j++)
  81.                     if (vertexCount[tree[sortedVertex[nodeIndex]][j]] == 1) {
  82.                         valid = false;
  83.                         break;
  84.                     }
  85.                 if (valid) {
  86.                     int connectedVertex = *tree[sortedVertex[nodeIndex]].begin();
  87.                     cout << connectedVertex << " ";
  88.                     vertexCount[connectedVertex]--;
  89.                     for (int ind = 0; ind < tree[connectedVertex].size(); ind ++)
  90.                         if (tree[connectedVertex][ind] == sortedVertex[nodeIndex]) {
  91.                             tree[connectedVertex].erase(tree[connectedVertex].begin() + ind);
  92.                             break;
  93.                         }
  94.                 }
  95.             }
  96.         }
  97.     }
  98.  
  99.     return 0;
  100. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top