题目描述

给定无向连通图 G 和 m 种不同的颜色。用这些颜色为图 G 的各顶点着色，每个顶点着一种颜色。如果有一种着色法使 G 中每条边的 22 个顶点着不同颜色，则称这个图是 m 可着色的。图的 m 着色问题是对于给定图 G 和 m 种颜色，找出所有不同的着色法。

输入

第 1 行有 3 个正整数n,k,m，表示给定的图 G 有 n 个顶点和 k 条边，m 种颜色。顶点编号为 1,2,…,m。接下来的 k 行中，每行有 2 个正整数 u,v，表示图 G 的一条边(u,v)。

输出

将计算出的不同的着色方案数输出。

样例输入输出

样例输入 #1

样例输出 #1

数据范围

数据保证，1≤n≤100，1≤k≤2500。

在 n 很大时保证 k 足够大。

保证答案不超过 20000。

数据为在满足上述条件的合法数据中随机采样得到。

差不多是这样的：

 分析：

        1.判断颜色是否符合要求 对于每个节点 u，如果它与另一个节点 v 有边相连，且这两个节点颜色相同，那么就不能把节点 u 涂为该颜色。因此，需要定义一个函数 ok() 来判断某个节点染上某种颜色是否符合要求。具体来说，ok(u, c) 函数返回值为true表示节点 u 可以涂上颜色 c，否则返回false。

      2.使用深度优先搜索

使用深度优先搜索（DFS）从解空间树的根节点开始搜索，并在每个分支结点处调用 ok() 函数来剪枝。如果在整棵解空间树中找到了一组可行解，那么算法就停止搜索并输出结果。如果找不到任何一个可行解，则算法输出无解信息。

具体实现过程：

首先，需要定义一个二维数组 G[ ][ ]，用于存储图中的边。其中，G[u][v] == 1 表示节点 u 和节点 v 之间有边相连，反之为 0。同时，还需要定义一个一维数组 color[ ]，用于存储每个节点的颜色。

首先将所有边权赋值为 0，即不存在边。然后，读入所有边，将对应的边权赋值为 1。读入颜色数 m，并从节点 1 开始做深度优先搜索，依次尝试给每个节点涂上不同的颜色。在每个分支结点处，使用 ok() 函数来判断是否符合要求。如果染色成功，则继续对下一个节点做深度优先搜索。如果找到了一组可行解，则输出结果

        3.时间复杂度（转载于kurayamasy的【时间复杂度计算方法以及常见的时间复杂度】链接：https://blog.csdn.net/m0_63850771/article/details/127229462）

概念：

  一般来说要确定算法的运行时间，只有你将他拿到机器上去测试一下才能确定，但是过于麻烦，那么有没有一种方法能够估算该算法的运行时间呢？因此引入了时间复杂度这个概念。

    时间复杂度是一种函数，定量地描述了该算法运行的时间。既然是一种函数，就涉及到自变量与因变量。因变量代表是时间复杂的规模，自变量是时间复杂度的执行时间。这里的执行时间并不是秒，分钟这类的具体时间  ，它表示的是一种“执行次数”。要想计算时间复杂度首先得找到该算法中的循环，算法中循环执行的次数就是算法的时间复杂度 。

     算法的时间复杂度的具体表示为：用大写的 O 来体现算法时间复杂度如O（f（n）），称之为 大 O 记数法。

算法：

一，给定 n个元素 的数组a[n]，求其中 奇数 有多少个。判断一个数是偶数还是奇数，只需要求它除上 2 的余数是 0 还是 1，把所有数都判断一遍，并且对符合条件的情况进行计数，最后返回这个计数器就是答案，需要遍历所有的数。

二，求下面函数的时间复杂度

int fun(int n) {    int cnt = 0;   for(int i = 0;i < n;i++)    {      for(int j = 0; j      ++cnt;    }//一层循环，循环n次      for(int l = 0;l    assert(a); for(int end = n; end>0; end--)     {       int exchange = 0;        for(int i = 1; i                 swap(&a[i],&a[i-1]);                  exchange = 1;                }             }             if(exchange==0)            break;      } }

例如在这个冒泡排序中,我们需要将无序数组转化为有序数组的一种算法,它并不像上题一样是简单的双层嵌套循环,很容易想到它的循环次数是一个等差数列,第一次循环n-1次,第二次n-2次.....一直到1.因此为n-1+n-2+n-3.....+1 = n*(n-1)/2,由上面所说的规律时间复杂度为O(N*N).

  通过上面的例子我们看出,大O渐近表示法去掉了对结果影响不大的项,简洁明了地表示出了时间复杂度.在实际情况中一般只关注算法的最坏运行情况.

   例如在上述冒泡排序中,如果给定的数组就已经是有序的了,那么就是它的最好情况,时间复杂度为O(N).但是如果有非常多的数据很显然我们看不出它到底是否为最好情况,所以我们必须用最坏的期望来计算所以它是O(N*N).

四, int fun(int n) {   int i = 0;int cnt = 0;    for( i; i     int left = 0, right = n - 1;     while(l     int i;     if(n == 1) {         return false;     }     int sqrtn = sqrt(n);     for(int i = 2; i             return false;         }     }     return true; }

只需要枚举所有小于根号n的数,使n与其相除 ,这样时间复杂度就小了很多.那为什么只需要枚举小于根号n个数呢?

因为假设n是数k的因子,那么n^2也必定是数k的因子,所以不需要枚举小于k这么多数,只需要枚举根号n个数就可以了.

6,阶乘阶 阶乘阶的讨论没有意义,阶乘级的时间复杂度一般在刷题时过不了,一般会用动态规划代替.

打住，文章似乎已经太长了  

代码区

考察点：

数组

dfs

scanf和printf（比cin cout快一点）

贴代码：