UVALive

n个点的一张图，问能否给每个点染上三种颜色中的一种，使得没有相邻的点颜色相同？

n <= 35。

Sample Input
4
6
6
0 3
1 5
3 2
2 5
0 4
1 0
7
12
6 5
0 3
2 6
3 5
5 0
0 4
4 5
6 3
1 4
1 2
3 4
2 3
7
8
6 5
0 3
2 6
3 5
1 4
1 2
3 4
2 3
6
9
0 1
1 2
2 3
5 2
5 3
3 4
2 4
1 4
4 5

Sample Output
Y
N
Y
N

　　

先想的求出最大团，然后如果最大团的点数 > 3一定不可以。

最大团的点数 <= 3呢？一定可以吗？不是这样的。

下面这个图最大团是3，然而也是不满足条件的。

可以搜索，枚举第一个点染的颜色，就可以3*2^(n-1)暴力。

然而有一个优化就是可以先求出所有的联通块，然后对每个联通块这样暴力。

场上写的T了。。被大佬们反杀。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
const int maxn = 30;
const int maxm = 1000;
const int INF=0x7f7f7f7f;

int v[maxm], nxt[maxm], last[maxm];
int vis[maxn], d[maxn];
vector<int> vc[maxn];
int sz = 0;
int n, m;

void DFS(int k, int p)
{
    vc[p].push_back(k);
    vis[k] = 1;
    for (int i = last[k]; i; i = nxt[i])
        if (!vis[v[i]]) DFS(v[i], p);
}

void init()
{
    sz = 0;
    for (int i = 0; i < maxn; i++) vc[i].clear();
    memset(last, 0, sizeof(last));
    memset(vis, 0, sizeof(vis));
    memset(d, 0, sizeof(d));
}

void build(int x, int y)
{
    sz++;
    v[sz] = y, nxt[sz] = last[x], last[x] = sz;
}

bool ok(int k)
{
    for (int i = last[k]; i; i = nxt[i])
        if (d[k] == d[v[i]]) return false;
    return true;
}

bool check(int p, int k)
{
    if (k == vc[p].size()) return true;
    int x = vc[p][k];
    for (int i = 1; i <= 3; i++)
    {
        d[x] = i;
        if (!ok(x)) continue;
        if (check(p, k+1)) return true;
    }
    d[x] = 0;
    return false;
}

int main()
{
    int t;
    scanf("%d", &t);
    for (int ca = 1; ca <= t; ca++)
    {
        init();
        scanf("%d%d", &n, &m);

        for (int i = 1; i <= m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            build(x, y), build(y, x);
        }

        int cnt = 0;
        for (int i = 0; i < n; i++)
            if (!vis[i])
            {
                ++cnt;
                DFS(i, cnt);
            }


        int flag = true;
        for (int i = 1; i <= cnt; i++)
            if (!check(i, 0)) { flag = false; break; }

        printf("%c
", flag ? 'Y':'N');

    }
}