【Codeforces 653E】Bear and Forgotten Tree 2

  这题复杂度好玄学...

  首先想怎么样可以生成一棵树。建出完全图，把所有的不在图中的边都去掉以后图还联通那肯定能生成一棵树了，然后剩下一端为1号点的边的数量大于等于1号点的度数就好了。

  直接连所有的边做一遍BFS，时间复杂度\(O(n^2)\)显然无法承受。然后标算就用一个未处理点的集合S，每次找一个点与其他点的连边时就在S里找，这么做时间复杂度稍微分析一下应该是\(O(n)\)的。

  标算开了两个set鬼知道它怎么跑过去的。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=300010;

struct Edge {int x,y;}E[maxn<<1];
bool cmp(const Edge &a,const Edge &b) {return a.x<b.x || a.x==b.x && a.y<b.y;}

int next[maxn],prev[maxn];
int In[maxn];
int con1[maxn];
int Eh[maxn];
int n,m,k,cnt;

int q[maxn];

void DFS(int x)
{
	int top=1,tail=1;
	q[1]=x;
	In[x]=0;
	next[prev[x]]=next[x];
	prev[next[x]]=prev[x];
	while (top<=tail)
	{
		x=q[top++];
		for (int i=next[1],j=Eh[x];i<=n;i=next[i])
		{
			while (j<Eh[x+1]-1 && E[j+1].y<=i) j++;
			if (E[j].x==x && i==E[j].y) continue;
			next[prev[i]]=next[i];
			prev[next[i]]=prev[i];
			In[i]=0;
			q[++tail]=i;
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	cnt=0;m<<=1;
	for (int i=1,x,y;i<=m;i+=2)
	{
		scanf("%d%d",&E[i].x,&E[i].y);
		E[i+1].x=E[i].y,E[i+1].y=E[i].x;
	}
	sort(E+1,E+1+m,cmp);
	for (int i=1;i<=m && E[i].x==1;i++) con1[E[i].y]=1,cnt++;
	if (cnt+k>=n) {puts("impossible");return 0;}
	for (int i=1,j=1;i<=m;i++) while (j<=E[i].x) Eh[j++]=i;Eh[n+1]=m+1;
	cnt=0;
	for (int i=2;i<=n;i++) In[i]=1,next[i]=i+1,prev[i]=i-1;
	next[1]=2;prev[n+1]=n;
	for (int i=2;i<=n;i++) if (In[i] && !con1[i]) DFS(i),cnt++;
	if (next[1]!=n+1) {puts("impossible");return 0;}
	if (cnt>k) {puts("impossible");return 0;}
	puts("possible");
	return 0;
}