当前位置：首页 > news >正文

UVA1613 K-Graph Oddity（无向图染色简单题）

news 来源：原创 2024/4/28 17:33:32

题目链接

在这里插入图片描述
1.题目大意：给出一个无向图，现在需要给每个节点染色，相邻节点颜色不同，输出最小的颜色数以及每个节点的颜色

2.第一次接触图论染色的题，实际上就是贪心，无权图的话度数最大的度数为奇数则就为最大奇数，否则则可以加一得到最大的奇数。那么直接暴力贪心即可

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

vector<int> G[maxn];
bool vis[maxn];
int degree[maxn],ans[maxn];
int x;

bool check(int u,int y){  //y颜色能否被染
    for(auto i : G[u]){ //遍历相邻点
        if(ans[i]==y) return 0;
    }
    return 1;
}

void dfs(int u){
    vis[u]=1;
    for(int j=1;j<=x;j++)
        if(check(u,j)){
            ans[u]=j;
            break;
        }
    for(auto i : G[u]){
        if(!vis[i]) dfs(i);
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m,a,b;
    while(cin>>n>>m){
        memset(degree,0,sizeof degree);
        memset(vis,0,sizeof vis);
        memset(ans,0,sizeof ans);
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=0;i<m;i++){
            cin>>a>>b;
            G[a].push_back(b);
            G[b].push_back(a);
            degree[a]++,degree[b]++;
        }
        x=-1;
        for(int i=1;i<=n;i++)
            x=max(x,degree[i]);
        if(!(x&1)) x++;
        cout<<x<<endl;
        dfs(1);
        for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
        cout<<endl;
    }
    return 0;
}