[Nowcoder199A] 分组(dfs，拉姆齐定理, 随机)

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://www.nowcoder.com/acm/contest/199/A

意思就是给你一个无向图染色，每个点最多有一个相邻点可以染成同色。

我们证明一下解一定存在：

首先考虑$n<4$，无论如何都能有解，显然成立。

我们可以画一下最极端的情况是什么样子的…

1538920651987

在这个情况下无法再想这个完全图内加边加点，因此这是个最极端的情况，但是它是有解的。

那么我们其他的符合条件的图都可以由这个图通过删边加点加边的方式获得并且他们是一个连通图（每个人都认识聚会中的一些人）。

于是这题就可以解了：

直接dfs，但是题目最后有个备注很蛋疼，那就是有10%的数据，有一组数据存在某个组里每个人都互相不认识。

所以我们考虑尽可能先处理那个分组里的点，这个分组里的点尽量首先安排。但是我们又不能知道那个组都有哪些个点，因此我们考虑把每一个点的边打乱一下保存再dfs，最后再加个特判就ok。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100100;
vector<int> G[maxn];
int vis[maxn];
int n, m;

void dfs(int u, int p, int id) {
  int cnt = 0;
  vis[u] = id;
  for(int i = 0; i < G[u].size(); i++) {
    int& v = G[u][i];
    if(v == p) continue;
    if(!vis[v]) dfs(v, u, 3-vis[u]);
    if(vis[v] == vis[u]) cnt++;
  }
  if(cnt >= 2) vis[u] = 3 - vis[u];
}

signed main() {
  // freopen("in", "r", stdin);
  int u, v;
  srand((unsigned)time(NULL));
  while(~scanf("%d%d",&n,&m)) {
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++) G[i].clear();
    for(int i = 0; i < m; i++) {
      scanf("%d%d",&u,&v);
      G[u].emplace_back(v);
      G[v].emplace_back(u);
    }
    for(int i = 1; i <= n; i++) {
      random_shuffle(G[i].begin(), G[i].end());
    }
    int cnt1 = 0, cnt2 = 0;
    for(int i = 1; i <= n; i++) {
      if(!vis[i]) dfs(i, -1, 2);
      if(i == n) {
        if(cnt1 == n - 1) printf("%d\n", 2);
        else if(cnt2 == n - 1) printf("%d\n", 1);
        else printf("%d%c",vis[i], " \n"[i==n]);
      }
      else printf("%d%c",vis[i], " \n"[i==n]);
      if(vis[i] == 1) cnt1++;
      else cnt2++;
    }
  }
  return 0;
}