UVA1613-K-Graph Oddity（贪心）

Problem UVA1613-K-Graph Oddity

Accept: 108  Submit: 884
Time Limit: 3000 mSec

Problem Description

Input

The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line.
The first line of the input file contains two integer numbers n and m, where n is the number of vertices in the graph (3 ≤ n ≤ 9999, n is odd), m is the number of edges in the graph (2 ≤ m ≤ 100000). The following m lines describe edges of the graph, each edge is described by two integers ai, bi (1 ≤ ai,bi ≤ n,ai = bi) — the vertex numbers connected by this edge. Each edge is listed at most once. The graph in the input file is connected, so there is a path between any pair of vertices.

 Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
On the first line of the output file write a single integer number k — the minimal odd integer number, such that the degree of any vertex does not exceed k. Then write n lines with one integer number ci (1 ≤ ci ≤ k) on a line that denotes the color of i-th vertex. The colors of any two adjacent vertices must be different. If the graph has multiple different colorings, print any of them. At least one such coloring always exists.

 

 Sample Input

3 2
1 3
3 2

7 8
1 4
4 2
2 6
6 3
3 7
4 5
5 6
5 2

 

Sample Output

3
1
1
2

 

3
1
1
1
2
3
2
2

 

题解：这个题过得比较意外，一开始想从度数大的开始涂，弄一个优先队列，画了几个图，发现好像不管怎么涂都对，就写了一个然后过了，为什么是对的真的说不好，欢迎大佬指教。

 

#include <bits/stdc++.h>

using namespace std;

const int maxn = 10000 + 10, maxm = 100000 + 10;

int n, m, k;

struct Edge {
    int to, next;
}edge[maxm << 1];

int tot, head[maxn];
int col[maxn], deg[maxn];
bool vis[maxn];

void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
    memset(deg, 0, sizeof(deg));
    memset(col, -1, sizeof(col));
}

void AddEdge(int u,int v){
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void dfs(int u) {
    memset(vis, false, sizeof(vis));
    //printf("%d %d
", fa, u);
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (col[v] != -1) vis[col[v]] = true;
    }

    for (int i = 1; i <= k; i++) {
        if (!vis[i]) {
            col[u] = i;
            break;
        }
    }

    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (col[v] == -1) {
            dfs(v);
        }
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    bool flag = false;
    while (~scanf("%d%d", &n, &m)) {
        if(flag) printf("
");
        flag = true;
        init();
        int x, y;
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &x, &y);
            deg[x]++, deg[y]++;
            AddEdge(x, y);
            AddEdge(y, x);
        }

        int Max = 0;
        for (int i = 1; i <= n; i++) {
            Max = Max > deg[i] ? Max : deg[i];
        }

        k = (Max & 1) ? Max : Max + 1;
        dfs(1);
        printf("%d
", k);
        for (int i = 1; i <= n; i++) {
            printf("%d
", col[i]);
        }
    }
    return 0;
}