Prüfer-Sequence(Tree-to-Sequence).cpp

#include <cstdio>
#include <queue>

#define VERTEX_COUNT 100010
#define EDGE_COUNT 200010

using namespace std;

struct vertex
{
	int first, subcnt, fa;
	bool vis;
}V[VERTEX_COUNT];

struct edge
{
	int endp, next;
}E[EDGE_COUNT];

int ivc, ec = 2, prufer[VERTEX_COUNT], pc;
priority_queue< int, vector<int>, greater<int> > Q;

inline void add_edge(int u, int v)
{
	E[ec].next = V[u].first;
	V[u].first = ec;
	E[ec].endp = v;
	ec++;
}

void dfs(int u, int fa)
{
	V[u].vis = true;
	V[u].fa = fa;
	for (int cur = V[u].first; cur != 0; cur = E[cur].next)
	{
		if (V[E[cur].endp].vis == false) dfs(E[cur].endp, u), V[u].subcnt++;
	}
}

int main()
{
	int u, v;
	scanf("%d", &ivc);
	for (int i = 1; i < ivc; i++)
	{
		scanf("%d%d", &u, &v);
		add_edge(u, v);
		add_edge(v, u);
	}
	dfs(1, 0);
	for (int i = 1; i <= ivc; i++)
	{
		if (E[V[i].first].next == 0) Q.push(i);
	}
	for (int i = 3; i <= ivc; i++)
	{
		int u = Q.top();printf("pop : %d, fa = %d\n", u, V[u].fa);
		Q.pop();
		if (V[u].fa == 0)
		{
			for (int cur = V[u].first; cur != 0; cur = E[cur].next)
			{
				if (V[E[cur].endp].fa != 0)
				{
					prufer[pc++] = E[cur].endp;
					V[E[cur].endp].fa = 0;
					if (V[E[cur].endp].subcnt == 1) Q.push(E[cur].endp);
					break;
				}
			}
		}
		else
		{
			prufer[pc++] = V[u].fa;
			V[V[u].fa].subcnt--;
			if (V[V[u].fa].subcnt == 0) Q.push(V[u].fa);
			else if (V[V[u].fa].subcnt == 1 && V[V[u].fa].fa == 0) Q.push(V[u].fa);
		}
	}
	for (int i = 0; i < pc; i++)
	{
		printf("%d ", prufer[i]);
	}
	return 0;
}