1069. Prufer Code

Time limit: 0.25 second
Memory limit: 8 MB A tree (i.e. a connected graph without cycles) with vertices is given (N?≥?2). Vertices of the tree are numbered by the integers 1,…,N. A Prufer code for the tree is built as follows: a leaf (a vertex that is incident to the only edge) with a minimal number is taken. Then this vertex and the incident edge are removed from the graph, and the number of the vertex that was adjacent to the leaf is written down. In the obtained graph once again a leaf with a minimal number is taken, removed and this procedure is repeated until the only vertex is left. It is clear that the only vertex left is the vertex with the number?N. The written down set of integers (N?1 numbers, each in a range from 1 to?N) is called?a Prufer code?of the graph. Your task is, given a Prufer code, to reconstruct a tree, i.e. to find out the adjacency lists for every vertex in the graph. You may assume that 2?≤?N?≤?7500

Input

A set of numbers corresponding to a Prufer code of some tree. The numbers are separated with a spaces and/or line breaks.

Output

Adjacency lists for each vertex. Format: a vertex number, colon, numbers of adjacent vertices separated with a space. The vertices inside lists and lists itself should be sorted by vertex number in an ascending order (look at sample output).

Sample

inputoutput

2 1 6 2 6	1: 4 6 2: 3 5 6 3: 2 4: 1 5: 2 6: 1 2

Problem Author:?Magaz Asanov
Problem Source:?Ural State Univerisity Personal Contest Online February'2001 Students Session Tags:?graph theory??(hide tags for unsolved problems) Difficulty: 522 題意：給出prufer code，要求求出原樹。 分析：知道prufercode之后就很簡單了。 1 /** 2 Create By yzx - stupidboy 3 */ 4 #include <cstdio> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cmath> 8 #include <deque> 9 #include <vector> 10 #include <queue> 11 #include <iostream> 12 #include <algorithm> 13 #include <map> 14 #include <set> 15 #include <ctime> 16 #include <iomanip> 17 using namespace std; 18 typedef long long LL; 19 typedef double DB; 20 #define MIT (2147483647) 21 #define INF (1000000001) 22 #define MLL (1000000000000000001LL) 23 #define sz(x) ((int) (x).size()) 24 #define clr(x, y) memset(x, y, sizeof(x)) 25 #define puf push_front 26 #define pub push_back 27 #define pof pop_front 28 #define pob pop_back 29 #define ft first 30 #define sd second 31 #define mk make_pair 32 33 inline int Getint() 34 { 35 int Ret = 0; 36 char Ch = ' '; 37 bool Flag = 0; 38 while(!(Ch >= '0' && Ch <= '9')) 39 { 40 if(Ch == '-') Flag ^= 1; 41 Ch = getchar(); 42 } 43 while(Ch >= '0' && Ch <= '9') 44 { 45 Ret = Ret * 10 + Ch - '0'; 46 Ch = getchar(); 47 } 48 return Flag ? -Ret : Ret; 49 } 50 51 const int N = 7510; 52 int n, arr[N]; 53 int cnt[N]; 54 priority_queue<int> que; 55 vector<int> ans[N]; 56 57 inline void Input() 58 { 59 int x; 60 while(cin >> x) 61 { 62 arr[n++] = x; 63 cnt[x]++; 64 } 65 n++; 66 } 67 68 inline void Solve() 69 { 70 for(int i = 0; i < n; i++) 71 if(!cnt[i + 1]) que.push(-(i + 1)); 72 for(int step = 1; step <= n - 1; step++) 73 { 74 int x = -que.top(), now = arr[step - 1]; 75 que.pop(); 76 if(!(--cnt[now])) que.push(-now); 77 ans[now].pub(x); 78 ans[x].pub(now); 79 } 80 81 for(int i = 1; i <= n; i++) 82 { 83 printf("%d:", i); 84 sort(ans[i].begin(), ans[i].end()); 85 int length = sz(ans[i]); 86 for(int j = 0; j < length; j++) 87 printf(" %d", ans[i][j]); 88 printf("\n"); 89 } 90 } 91 92 int main() 93 { 94 freopen("a.in", "r", stdin); 95 Input(); 96 Solve(); 97 return 0; 98 } View Code

?

轉載于:https://www.cnblogs.com/StupidBoy/p/5076812.html

總結

以上是生活随笔為你收集整理的ural 1069. Prufer Code的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。