【习题 8-9 1613】 K-Graph Oddity

在这里输入题意

【题解】

感觉最大度数|1就是最多需要的个数了。
就贪心一下。
然后模拟染色的过程就可以了。
(贪心染色就可以了
(看看周围哪个颜色没有，就用它)
k在dfs之前忘记判断是不是奇数了。。。。
以及忘记清空g

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4;

int n,m,du[N+10],k,flag[N+10];

vector <int> g[N+10];

set<int>myset[N+10];

int ma;

void dfs(int x){

    myset[x].clear();

    for (auto y:g[x])

        if (flag[y]!=0){

            myset[x].insert(flag[y]);

        }

    for (int i = 1;i <= k;i++)

        if (myset[x].find(i)==myset[x].end()){

            flag[x] = i;

            break;

        }

    for (auto y:g[x])

        if (flag[y]==0)

            dfs(y);

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    while (cin >> n >> m){

        for (int i = 1;i <= n;i++) {

            g[i].clear();

            du[i] = 0;

            flag[i] = 0;

        }

        for (int i = 1;i <= m;i++){

            int x,y;

            cin >> x >> y;

            g[x].push_back(y);

            g[y].push_back(x);

            du[x]++;du[y]++;

        }

        k = 0;

        for (int i = 1;i <= n;i++)

            k = max(k,du[i]);

        if (!(k&1)) k++;

        dfs(1);

        cout <<k<<endl;

        for (int i = 1;i <= n;i++) cout << flag[i]<<endl;

        cout << endl;

    }

	return 0;

}

巴特西

【习题 8-9 1613】 K-Graph Oddity

最新文章

热门文章