染色过程 c++版

课设-染色问题

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 50;
int v, e, m;
int flag = 0;
int vis[MAXN];          //vis[i] = x  第i个点用x颜色染色.
vector<int> G[MAXN];    //用向量vector来存图，G[u]中有值v1,v2,v3...说明u -- v1, u -- v2, u -- v3, ...
void add_edge(int u, int v)     //加入边.
{
    G[u].push_back(v);     
    return;
}
void dfs(int now)        //用深度搜索来解决这个问题.先把now这个结点染上一种和它所连接的点都不冲突的颜色，然后再染now + 1这个点，如果把v个点都成功染色了，那么这个问题就得到了解决.如果在第v个点染色之前，m种颜色就不够用了，那说明m种颜色解决不了这个问题.
                        //但这个问题比较经典哈，人类运用计算机已经完全攻克图染色问题了.任何一张图（无论有几个结点，什么样的边）最多用四种颜色都能成功染色.
{
    if(now == v + 1){             //到第v + 1个点，这说明前v个点已经染色成功了.
        flag = 1;
        return;
    }
    for(int i = 1; i <= m; i ++){     //m种颜色挨个试一下.
        int t = 1;
        for(int j = 0; j < G[now].size(); j ++){                //与now结点连着的点有没有颜色相同的.
            int v = G[now][j];
            if(vis[v] == i){
                t = 0;
                break;
            }
        }
        if(t){                                     //如果now点染成i可行，那么往下继续搜索，dfs(now + 1).
            vis[now] = i;
            dfs(now + 1);
            if(flag)                                //问题已经解决，找到了一组解，直接结束.
                return;
        }
    }
}
int main()
{
    scanf("%d%d%d", &v, &e, &m);
    for(int i = 0; i < e; i ++){                   //输入边.
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    dfs(1);
    if(flag)
        for(int i = 1; i <= v; i ++)
            cout << i << " " << vis[i] << endl;
    else
        cout << "染色失败.";
    return 0;
}