题解

题目类型：图论 / DFS 连通块 / 贪心着色（两类标记）
输出格式：若存在可行标记则输出 TAK 并逐点输出字符，否则输出 NIE。

一、题意（从代码语义抽象）

给定一张无向图（n 个点、m 条边）。需要把每个点标记为两类之一（用字符 S 或 K 表示）。
代码的策略是在每个连通块内，按照 DFS 的遍历顺序给点赋值，使得：

• 若当前点的邻居中不存在某种标记，就把当前点赋成这种“缺失的标记”（优先补齐邻居中没有的颜色）；
• 若两种标记在邻居中都出现了，则任选一种（代码用 rand()%2+1 随机）。

此外，若连通块的大小为 1（孤立点），程序视为不满足题意并输出 NIE；否则所有连通块都能成功标记时输出 TAK 与整图标记方案。

直观理解：只要连通块里至少有一条边，按上述“补缺着色”的贪心过程就能给整个块分配上 S/K。唯独孤立点因没有邻居，按题意（需要与邻居形成某种关系）无法满足，故判负。

二、核心做法

1）建图

• 用邻接表存无向图：每条输入边 (u,v) 调用两次 add，分别加入 u→v 与 v→u。

2）DFS 赋标与统计连通块大小

• vis[u] 取值：0（未访问）、1（标为 S）、2（标为 K）。
• 在 dfs(u) 中，先看所有邻居 v 的状态：
  • f1：邻居里是否出现了 S；
  • f2：邻居里是否出现了 K。
• 赋值规则：
  • 如果邻居里没有 S，则给 u 标 S（vis[u]=1）；
  • 否则如果邻居里没有 K，则给 u 标 K（vis[u]=2）；
  • 否则两色都存在，任选一种（代码里随机为 1 或 2）。
• 之后对尚未访问的邻居递归 dfs，dfs 的返回值 siz 统计本次 DFS 所在连通块的结点数。

3）整体流程与判定

• 主程序遍历所有点 i：若未访问，则以 i 为起点做一次 dfs：
  • 若本连通块大小 siz==1（即 dfs(i)==1），直接输出 NIE 并结束；
  • 否则继续处理其他连通块。
• 若不存在孤立点：输出 TAK，随后对每个点输出其标记（vis[i]==1 输出 S，否则输出 K）。

三、正确性与细节

• 为何只要没有孤立点就能输出：
  在每个连通块中，初始时没有标记；当遍历到一个点时，若它的某个颜色在邻居中缺失，就把它涂成这种“缺失色”，从而尽可能丰富邻域的颜色分布。若两色都已在邻居出现，则任选一种也不会影响继续向外扩展地着色。
  唯一的例外是孤立点：它没有邻居，不能与任何点形成需要的邻接关系（题目对孤立点不满足要求，因此判为不可行）。

• 随机分配是否会影响可行性：
  不会。随机只发生在“邻居两色皆有”的情况下，说明无论选哪色，都不影响继续完成整个连通块的标记。

• 多连通块处理：
  各连通块独立处理，存在任一大小为 1 的块即整体输出 NIE。

四、复杂度分析

• 建图与 DFS 总计 O(n + m)；
• 常数开销很小，可应对 n ≤ 2e5, m ≤ 5e5 量级。

五、实现（与题给代码一致）

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e5 + 5, M = 5e5 + 5;
int n, m;
vector<int> g[N];
inline void add(int u, int v) { g[u].push_back(v); }
int vis[N];
int dfs(int u)
{
 bool f1 = false, f2 = false;
 for (int v : g[u]) f1 |= (vis[v] == 1), f2 |= (vis[v] == 2);
 if (!f1) vis[u] = 1;
 else if (!f2) vis[u] = 2;
 else vis[u] = rand() % 2 + 1;
 int siz = 1;
 for (int v : g[u])
  if (!vis[v]) siz += dfs(v);
 return siz;
}
int main()
{
 cin.tie(0)->sync_with_stdio(false);
 cout.tie(0);
 cin >> n >> m;
 for (int i = 1, u, v; i <= m; i++) cin >> u >> v, add(u, v), add(v, u);
 for (int i = 1; i <= n; i++)
  if (!vis[i])
   if (dfs(i) == 1) return cout << "NIE\n", 0;
 cout << "TAK\n";
 for (int i = 1; i <= n; i++)
 {
  if (vis[i] == 1) cout << "S\n";
  else cout << "K\n";
 }
 return 0;
}