自动搬运

查看原文

来自洛谷，原作者为

	dingcx 不如回头再看一眼题面

搬运于2025-08-24 21:49:32，当前版本为作者最后更新于2019-11-12 22:38:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题标签是广搜，于是我就用深搜来做。

不要问我为什么快考CSP了还来发题解

思路

首先看题：白点或黑点都只需要旁边有一个另一种颜色的点就行了，而灰色不一样，它需要一白一黑。显然，灰色要求更多，也就更难处理，那么，就不涂它了吧。

一个点白点或黑点，只要有点与它相连，这两个点颜色相反，就可以满足。而如果一个点不与其他任何点连通，不管涂不涂灰色，都无法满足。也就是说，在任何情况，都可以不涂灰色。

世界一下子清静了许多：只有黑点和白点。那么，对于每一个连通图，都搜一遍，第一个点记为白点，后面每搜到一个点，都涂上与前一个点相反的颜色，如果涂过就不涂了。而如果有一个连通图只有一个点，那么一定不行，输出$NIE$就好了。

细节

有的细节还是有必要提一下。

在读入边的时候，把这个边两个端点都标记一下，这样只要有没标记到的点，一定是单独的，即无法完成。

建边时，要用邻接表优化空间，不然会超空间。

深搜时，一定要没有搜到（新的连通图）再继续搜，不然绝对超时。

技巧

这里的技巧就是如何把代码写的更简单（更短）

判断是否搜过

开一个整型的$color$数组，值为$0$表示未染色（未遍历），$1$表示白色，$2$表示黑色。

判断只需要$color[i]==0$

求相反颜色

求相反颜色方法：$color[i]$%$2+1$（$1$直接变$2$，$2$直接变$1$）。

代码

相信没有多少人喜欢上面的一通分析吧，那么，你们喜欢的代码来了——

#include<cstdio>
using namespace std;
const int MAXN=200010,MAXM=1000010;//注意边数要乘2
int h[MAXN],color[MAXN],tot=0;//h为邻接表中的head，tot为总边数
bool vis[MAXN];//记录是否有连接
struct Edge{//边的结构体
	int v;
	int next;//next记录这条边在邻接表中指向同端点的另一条边
}e[MAXM];
void addEdge(int u,int v){//建边
	tot++;
	e[tot].v=v;
	e[tot].next=h[u],h[u]=tot;
}
void dfs(int u){//深搜，u为原节点，保证已染色
	for(int k=h[u];k;k=e[k].next){//邻接表查找
		int v=e[k].v;
		color[v]=color[u]%2+1;//公式
	}
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	while(m--){
		int uu,vv;
		scanf("%d%d",&uu,&vv);
		vis[uu]=1,vis[vv]=1;//记录
		addEdge(uu,vv);addEdge(vv,uu);//建边
	}
	for(int i=1;i<=n;i++)//判断是否不行
	    if(!vis[i]){
	    	printf("NIE\n");//输出
	    	return 0;//返回
		}
	printf("TAK\n");//直接输出
	for(int i=1;i<=n;i++)//每个点都搜一遍
		if(!color[i]){//没搜过
			color[i]=1;//先设为白点
			dfs(i);//开搜
		}
	for(int i=1;i<=n;i++){//输出
		if(color[i]==1) printf("K\n");
		else printf("S\n");
	}
	return 0;//华丽结束
}

在CSP前写一篇题解也不容易，别忘了点个赞！