自动搬运

查看原文

来自洛谷，原作者为

	honglan0301 AFO —— 只是我的心一直在问，用什么把你永久留下～ | 2024.07.25 — ？

搬运于2025-08-24 22:15:34，当前版本为作者最后更新于2023-05-14 11:43:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

一个渐进更优但是在这题数据范围下跟 $O({knm\over \omega})$ 暴力差不多的做法。

首先我们观察 $\text{C-Algae}$ 的性质，发现这两种操作是对称的，所以有：若 $G$ 为 $\text{C-Algae}$，则 $G$ 的补图也为 $\text{C-Algae}$（反之同理），原因是补图可以每次用与原图相反的合并方式造出来。于是我们会了一个暴力做法，即考虑倒推操作，交替进行以下两个拆分步骤，若最终能把图全都拆成单点则说明该图为 $\text{C-Algae}$。

1. 把原图分成多个不连通的子图（求连通块），然后分别检查各个子图。

2. 要么把反图分成多个不连通的子图（求反图连通块），然后分别检查各个子图的反图。

分析时间复杂度。单次操作 $1,2$ 分别是 $O(m)$ 和 $O(n^2-m)$ 的，而操作 $2$ 若能有效会消耗掉至少 $O(n)$ 条边，故至多进行 $O({m\over n})$ 轮，时间复杂度 $O(knm)$。

接下来考虑优化拆分的步骤。发现我们应该不同情况差别对待地对操作 $1,2$ 采取不一样的方式求连通块。操作 $1$ 在稀疏图上可以直接枚举边，单次时间复杂度 $O(n+m)$。而操作 $2$ 的图过于稠密，可以枚举点然后检查不存在的边，因为至多会查到 $m$ 条不存在的边，故单次时间复杂度同样为 $O(n+m)$。由于 $m\leq n^2$，故总时间复杂度 $O(k(n+m)\times{\min(m,n^2)\over n})=O(k(n+m)\sqrt m)$，常数不大，可以通过本题。

代码

实现可见下面代码，感觉还算简洁。

/*
  author: PEKKA_l  
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
#define pb push_back

int T,n,m,u,v;
vector <int> e[10005];
unordered_map <int,int> s;
bool isb(int x,int y) {if(x>y) swap(x,y); return s.count(x*20000+y);}

int zta[10005],ztb[10005],ztc[10005],cntb,cntc,sza[10005],szc[10005];
int nowb[10005],nxt[20005],frm[20005];

queue <int> Q;
void ins(int k,int x) {nxt[nowb[k]]=x; frm[x]=nowb[k]; nowb[k]=x;}
void del(int x) {nxt[frm[x]]=nxt[x]; frm[nxt[x]]=frm[x]; }
void bfs(int x,int k)
{
	Q.push(x); ztb[x]=cntb; ins(ztb[x],x);
	while(!Q.empty())
	{
		int nr=Q.front(); Q.pop();
		for(auto i:e[nr]) {if(!ztb[i]&&zta[i]==k) {ztb[i]=cntb; Q.push(i); ins(ztb[i],i);}}
	}
}
void bfs2(int x,int k)
{
	Q.push(x); ztc[x]=cntc; szc[cntc]++; del(x);
	while(!Q.empty())
	{
		int nr=Q.front(); Q.pop();
		for(int i=nxt[k+10000];i;i=nxt[i])
		{
			if(!isb(nr,i)) {ztc[i]=cntc; szc[cntc]++; del(i); Q.push(i);}
		}
	}
}
void czc(int k) {while(nxt[k+10000]) {int nr=nxt[k+10000]; cntc++; bfs2(nr,k);}}

signed main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>m; s.clear(); for(int i=1;i<=n;i++) e[i].clear();
		for(int i=1;i<=m;i++) {cin>>u>>v; if(u>v) swap(u,v); e[u].pb(v); e[v].pb(u); s[u*20000+v]=1;}
		for(int i=1;i<=n;i++) zta[i]=1; sza[1]=n;
		while(1)
		{
			memset(ztb,0,sizeof(ztb)); cntb=0; for(int i=1;i<=n;i++) nowb[i]=i+10000;
			memset(nxt,0,sizeof(nxt)); memset(frm,0,sizeof(frm));
			for(int i=1;i<=n;i++) if(!ztb[i]) {cntb++; bfs(i,zta[i]);}
			memset(ztc,0,sizeof(ztc)); cntc=0; memset(szc,0,sizeof(szc));
			for(int i=1;i<=cntb;i++) czc(i);
			bool yes=1,no=0;
			for(int i=1;i<=n;i++)
			{
				if(sza[zta[i]]==szc[ztc[i]]) no=1;
				if(szc[ztc[i]]>2) yes=0;
			}
			if(no) {cout<<"NIE"<<endl; break;}
			if(yes) {cout<<"TAK"<<endl; break;}
			memcpy(zta,ztc,sizeof(ztc)); memcpy(sza,szc,sizeof(szc));
		}
	}
}