【BZOJ1006】神奇的国度（弦图）

题面

BZOJ

题解

直接参考弦图的做法

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define MAXL 1200000

#define MAX 12000

inline int read()

{

    int x=0,t=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Line{int v,next;}e[MAXL<<1];

int h[MAX],cnt=1;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

vector<int> V[MAX];

int n,m,label[MAX],best,ans,Q[MAX],tot;

bool vis[MAX];

int main()

{

	n=read();m=read();

	for(int i=1,u,v;i<=m;++i)

	{

		u=read(),v=read();

		Add(u,v);Add(v,u);

	}

	for(int i=1;i<=n;++i)V[0].push_back(i);best=0;

	for(int i=1,now=0;i<=n;++i)

	{

		bool fl=false;

		while(!fl)

		{

			for(int j=V[best].size()-1;j>=0;--j)

				if(vis[V[best][j]])V[best].pop_back();

				else{fl=true;now=V[best][j];break;}

			if(!fl)--best;

		}

		Q[++tot]=now;vis[now]=true;

		for(int j=h[now];j;j=e[j].next)

			if(!vis[e[j].v])

				V[++label[e[j].v]].push_back(e[j].v),best=max(best,label[e[j].v]);

	}

	for(int i=1;i<=n;++i)ans=max(ans,label[i]+1);

	printf("%d\n",ans);

}