URAL 1069 Prufer Code 优先队列

记录每个节点的出度，叶子节点出度为0，每删掉一个叶子，度数-1，如果一个节点的出度变成0，那么它变成新的叶子。

先把所有叶子放到优先队列中。

从左往右遍历给定序列，对于root[i]，每次取出叶子中编号最小的那个与root[i]相连，并且--degree[ root[i] ]，如果degree[ root[i] ]为0，那么把root[i]放入优先队列。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 
 8 using namespace std;
 9 
10 const int MAXN = 7510;
11 
12 struct LLL
13 {
14     int lf;
15     LLL( int nn = 0 ): lf(nn) { }
16     bool operator<( const LLL& rhs ) const
17     {
18         return lf > rhs.lf;
19     }
20 };
21 
22 int vis[MAXN];
23 vector<int> Tr[MAXN];
24 int num[MAXN];
25 priority_queue<LLL> leaf;
26 
27 int main()
28 {
29     int cnt = 0;
30     int N = 0;
31     while ( scanf( "%d", &num[cnt] ) != EOF )
32     {
33         N = max( N, num[cnt] );
34         ++cnt;
35     }
36 
37     memset( vis, 0, sizeof(vis) );
38     for ( int i = 0; i < cnt; ++i )
39         ++vis[ num[i] ];
40 
41     for ( int i = 1; i <= N; ++i )
42         if ( vis[i] == 0 ) leaf.push( LLL(i) );
43 
44     for ( int i = 1; i <= cnt; ++i ) Tr[i].clear();
45 
46     int i, j;
47     for ( i = 0; i < cnt; ++i )
48     {
49         LLL tmp = leaf.top();
50         leaf.pop();
51         Tr[ num[i] ].push_back( tmp.lf );
52         Tr[ tmp.lf ].push_back( num[i] );
53         --vis[ num[i] ];
54         if ( vis[ num[i] ] == 0 )
55             leaf.push( LLL( num[i] ) );
56     }
57 
58     for ( i = 1; i <= N; ++i )
59     {
60         printf( "%d:", i );
61         sort( Tr[i].begin(), Tr[i].end() );
62         int sz = Tr[i].size();
63         for ( j = 0; j < sz; ++j )
64             printf(" %d", Tr[i][j] );
65         puts("");
66 
67     }
68     return 0;
69 }