11分代码求调

#include <iostream>
#include <vector>
using namespace std;

const int INF=1919810;
const int maxn=300001;
int n,cnt,a,b;
int choose[maxn];
int deg[maxn];
struct nodes 
{
	int id,l,r,deg;
};

nodes node[4*maxn];

void build(int i,int l,int r)
{
	node[i].l=l;
	node[i].r=r;
	if (l==r)
	{
		node[i].deg=deg[l];
		node[i].id=l;
		return;
	}
	int mid=(l+r)>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	if (node[i*2].deg<node[i*2+1].deg)
	{
		node[i].deg=node[i*2].deg;
		node[i].id=node[i*2].id;
	}
	else
	{
		node[i].deg=node[i*2+1].deg;
		node[i].id=node[i*2+1].id;
	}
}

void update(int i,int l,int r,int pos,int newval)
{
	if (l==r)
	{
		node[i].deg+=newval;
		return;
	}
	int mid=(l+r)>>1;
	if (pos<=mid)
	{
		update(i*2,l,mid,pos,newval);
		if (node[i*2].deg<=node[i*2+1].deg)
		{
			node[i].deg=node[i*2].deg;
			node[i].id=node[i*2].id;
		}
		else
		{
			node[i].deg=node[i*2+1].deg;
			node[i].id=node[i*2+1].id;
		}
	}
	else
	{
		update(i*2+1,mid+1,r,pos,newval);
			if (node[i*2].deg<node[i*2+1].deg)
	{
		node[i].deg=node[i*2].deg;
		node[i].id=node[i*2].id;
	}
	else
	{
		node[i].deg=node[i*2+1].deg;
		node[i].id=node[i*2+1].id;
	}
	}

}
struct edge
{
	int u,v;
	bool wipe;
};
edge edges[3*maxn];
vector<int>G[maxn];
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		edges[i].u=i;
		edges[i].v=i%n+1; 
		edges[i].wipe=0;
		G[i].push_back(i);
		G[i%n+1].push_back(i);
		deg[i]=2;
	}
	for (int i=n+1;i<=2*n-3;i++)
	{
		cin>>edges[i].u>>edges[i].v;
		edges[i].wipe=0;
		G[edges[i].u].push_back(i);
		G[edges[i].v].push_back(i);
		deg[edges[i].u]++;
		deg[edges[i].v]++;
	}
	if (n&1)
	{
		cout<<-1<<endl;
		return 0;
	}
	build(1,1,n);
	while (cnt<n)
	{
		a=b=0;
		int pos=node[1].id;
		choose[pos]=1;
		cnt++;
		int sz=G[pos].size();
		update(1,1,n,pos,INF);
		if (deg[pos]%2==0)
		{
			for (int j=0;j<sz;j++)
			{
				edge &e=edges[G[pos][j]];
				if (!e.wipe&&(choose[e.u]==0||choose[e.v]==0))
				{
					e.wipe=1;
					deg[e.u]--;
					deg[e.v]--;//删掉(u,v) 
					update(1,1,n,(pos==e.u?e.v:e.u),-1);
					for (int k=j+1;k<sz;k++)
					{
						edge f=edges[G[pos][k]];
						if (!f.wipe&&(choose[f.u]==0||choose[f.v]==0))
						{
							update(1,1,n,(pos==f.u?f.v:f.u),-1);
							break;
						}
					}
					break;
				}
			}
		}
		else
		{
			for (int j=0;j<sz;j++)
			{
				edge &e=edges[G[pos][j]];
				if (!e.wipe&&(choose[e.u]==0||choose[e.v]==0))
				{
					//e.wipe=1;
					if (!a)
					{
						a=(pos==e.u?e.v:e.u);
						update(1,1,n,a,-1);
					}
					else
					{
						b=(pos==e.u?e.v:e.u);
						update(1,1,n,b,-1);
					 } 
				}
			}
			if (a&&b)
			{
				int s=G[a].size();
				for (int k=0;k<s;k++)
				{
					edge &e=edges[G[a][k]];
					if ((e.u==a&&e.v==b)||(e.u==b&&e.v==a))
					{
						deg[a]--;
						deg[b]--;
						e.wipe=1;
						update(1,1,n,a,-1);
						update(1,1,n,b,-1);
					}
				}
			}
		}
	}
	for (int i=1;i<=2*n-3;i++)
	{
		if (!edges[i].wipe)
		{
			cout<<edges[i].u<<" "<<edges[i].v<<endl;
		}
	}
}