rt

这题在按秩合并时有这样一行代码：

if(deg[x]<deg[y]) swap(x,y);

喜提 $10 \operatorname{pts}$

调 $20$ 分钟后发现改成

if(deg[x]<=deg[y]) swap(x,y);

可以过掉 #$2$。

再改半个小时后突发奇想，改成了

if(deg[x]<=deg[y]+1) swap(x,y);

于是 A 了。

完整代码：

#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 10000005
using namespace std;
inline ll read()
{
    rll x=0;bool f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-') f=0;c=getchar();}
    while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
    return f?x:-x;
}
inline void write(ll x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
ll n=read(),m=read(),sb,idx,idxc,head,tail,q[N<<1],c[N],f[N],v[N],h[N],ne[N],deg[N];
inline void add(ll x,ll y){v[++idx]=y,ne[idx]=h[x],h[x]=idx,deg[x]++;}
inline ll find(ll x)
{
	if(x==f[x]) return x;
	return f[x]=find(f[x]); 
}
inline void merge(ll x,ll y)
{
	x=find(x),y=find(y);
	if(x==y) return;
	if(deg[x]<=deg[y]+1) swap(x,y);
	f[y]=x,deg[x]+=deg[y];
	for(rll i=h[y];~i;i=ne[i])
		add(x,v[i]);
}
inline void dfs(ll x)
{
	rll t=find(v[h[x]]);
	for(rll i=ne[h[x]];~i;i=ne[i])
		merge(v[i],t);
	ne[h[x]]=-1,deg[x]=1;
	if(deg[t]>1) dfs(t);
}
int main()
{
	memset(h,-1,sizeof h);
	for(rll i=1;i<=n;i++) f[i]=i;
	for(rll i=1;i<=m;i++)
	{
		cll x=read(),y=read();
		add(x,y);
	}
	for(rll i=1;i<=n;i++)
		if(deg[i]>1) dfs(i);
	for(rll i=1;i<=n;i++)
		if(!c[find(i)]) c[find(i)]=++idxc;
	for(rll i=1;i<=n;i++)
		write(c[find(i)]),putchar('\n');
    return 0;
}

至于为什么是第九大奇迹，您可以自行向 @kongdechangjun 咨询第八大奇迹。