现金酬谢！关于图的二着色的问题，C语言大手子帮帮我

1、描述一下具体输入，比如上图一，长这样？？还是邻接矩阵？还是直接一堆边？

5

4 2

1 5

5

1 5

2 3 4

2、你这个问题本质上属于二分图染色。。你可以百度找一下资料

我写过二分图匹配的题可以参考，，，。迟耐提交：

代码网页链接

//二分图最大匹配 O(V*E) Test#include<iostream>#include<vector>#include<cstring>using namespace stdconst int N = 3e6vector<int>G[N]int po[N], book[N], ansint find(int u){

    for(int i = 0 i < G[u].size() i++){

        int v = G[u][i]

        if(!book[v]){

            book[v] = 1

            if(po[v]==0||find(po[v])){

                po[v] = u

                return true

            }

        }

    }

    return false}int main(){

    int nl, nr, m

    cin>>nl>>nr>>m

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

        int x, y  cin>>x>>y

       慎旦核 G[y].push_back(x)

    }

    for(int i = 1 i <= nr i++){

        memset(book,0,sizeof(book))

        if(find(i)){

            ans++

        }

    }

    宽掘cout<<ans<<"\n"

    for(int i = 1 i <= nl i++)cout<<po[i]<<" "

    return 0}

道路着色问题（Road Coloring Problem）是图论中最著名的猜想之一。通俗的说，这个猜想认为，可以绘制一张“万能地图”，指导人们到达某一目的地，不管他们原来在什么位置。这个猜想最近被以色列数学家艾夫拉汉· 特雷特曼(Avraham Trahtman)在2007年9月证明。

举个例子。在维基网给出的图例中，如果按图中所示方式将16条边着色，那么不管你从哪里出发，按照“蓝红红蓝红红蓝红红”的路线走9步，你最后一定达到黄色顶点。路线着色定理就是说在满足一定条件的有向图中，这样的着色方式一定存在。严格的数学描述如下。我们首先来定义同步着色。G是一个有限有向图并且G的每个顶点的出度都是k。G的一个同步着色满足以下两个条件：1)G的每个顶点有且只有一条出边被染成了1到k之间的某种颜色；2)G的每个顶点都对应一种走法，不管你从哪里出发，按该走法走，最后都结束在该顶点。有向图G存在同步着色的必要条件是G是强连通而且是非周期的。一个有向图是非周期的是指该图中包含的所有环的长度没有大于1的公约数。路线着色定理这两个条件(强连通和是非周期)也是充分的。也就是说,有向图G存在同步着色当且仅当G是强连通而且是非周期的。

特雷特曼在数学上的这一成果极为令人瞩目，英国《独立报》为此事专门发表了一篇题为“身无分文的移民成了数学超级明星”的文章，给予了高度的评价。

以色列人也为特雷特曼取得的成就感到无比的骄傲。特拉维夫电视台中断了正常的节目播放，以第一时间发布了这一重大消息，连中东其他国家的主流媒体也作了大篇幅的相关报道。

得知特雷特曼解决这一难题的消息后，多年从事路线着色问题研究的加拿大数学家乔尔·弗里德曼说，“路线着色问题的解决令数学共同体非常兴奋。”读过特雷特曼论文的中国数学家和语言学家周海中教授认为，特雷特曼的数学知识非裤瞎常渊博，解题方法十分巧妙，这一谜题得到破解，无疑是数学史上的一个华彩乐章。 算法描述：color[n]存储n个顶点的着色方案，可以选择的颜色为1到m。

当t=1时，对当前第t个顶点开始着色：若t>n，则已求得一个解，输出着色方案即可。否则，依次对顶点t着色1-m， 若t与所有其它相邻顶点无颜色冲突，则继续为下一顶点着色；否则，回溯，测试下一颜色。 #include<stdio.h>intcolor[100]boolok(intk,intc[][100])//判断顶点k的着色是否发生冲突{inti,jfor(i=1i<ki++){if(c[k][i]==1&&color[i]==color[k])returnfalse}returntrue}voidgraphcolor(intn,intm,intc[][100]){inti,kfor(i=1i<=ni++)color[i]=0k=1while(k>=1){color[k]=color[k]+1while(color[k]<=m)if(ok(k,c))breakelsecolor[k]=color[k]+1//搜索下一个颜色if(color[k]<=m&&k==n){for(i=1i<=ni++)printf(%d,color[i])printf(\n)}elseif(color[k]<=m&&k<n)k=k+1//处理下一个顶点else{color[k]=0k=k-1//回溯}}}voidmain(){inti,j,n,mintc[100][100]//存储n个顶点的无向图的数组printf(输入顶点数n和着色数m:\n)scanf(%d%d,&n,&m)printf(输入无向图的邻接矩阵:\n)for(i=1i<=ni++)for(j=1j<=nj++)scanf(%d,&耐纯穗c[i][j])printf(着色所有可能的解:\n)graphcolor(n,m,c)} 利用相交图（interference graph）来表示程序变量的生命期是否相交，将寄存器分配给变量的问题，可以近似地看成是给相交图着色：相交图中，相交的节点不能着同一颜色；每一种颜色对应一个昌卜寄存器。Chaitin等人最早提出了基于图着色的寄存器分配方法其着色思路采用了Kempe的着色方法，即，任意一个邻居节点数目少于k的节点，都能够被k着色。判断一个图是否能够被k(k>=3)种颜色着色，即k着色问题，被Karp证明是一个NP-complete问题。

但是，寄存器分配不仅仅是图着色的问题。当寄存器数目不足以分配某些变量时，就必须将这些变量溢出到内存中，该过程成为spill。最小化溢出代价的问题，也是一个NP-complete问题。如果简化该问题——假设所有溢出代价相等，那么最小化溢出代价的问题，等价于k着色问题，仍然是NP-complete问题。

此外，如果两个变量的生命期仅仅因为出现在同一个拷贝指令中而相邻，那么，通过将这两个变量分配到同一个寄存器，就可以消除该拷贝指令，成为coalescing。这个方向的努力在Chaitin的文章以后的1/4个世纪，成为推动寄存器分配的主要动力之一，涌现出了包括aggressive coalescing,conservative coalescing和optimistic coalescing。但是，将两个变量分配到同一个寄存器，等价于将这两个变量合并成同一个变量，生命期合并，因而会加剧相交图的聚簇现象，降低相交图的可着色性。Bouchez等人证明了目前的coalescing问题都是NP-complete的。

为了降低相交图的聚簇现象，提高相交图的可着色性，可以通过将变量拷贝给一个临时变量，并将以后对该变量的使用替换成对该临时变量的使用，从而将一个变量的生命期分解成两个变量的生命期，称为live range splitting。显然，这是一个与coalescing的作用相反的过程。Bouchez等人考虑了该方法的复杂度。

此外，寄存器分配还需要考虑寄存器别名(aliasing)和预着色(pre-coloring)的问题。寄存器别名是指，在某些体系结构中，一个寄存器的赋值可能会影响到另外一个寄存器。比如，在x86中，对AX寄存器的赋值，会影响AL和AH寄存器。预着色是指，某些变量必须被分配到特定的寄存器。比如，许多体系结构会采用特定寄存器来传递函数参数。

George和Appel发展了Chaitin的算法，更好地考虑了coalescing过程和赋值过程，以及各过程之间的迭代，在基于图着色的寄存器分配方法中具有广泛的影响。

一、求出这个图的补图　 （1）输入无向图的各边所关联的顶点对，确定每个顶点度，以及图的最大度数和最小度数，求出这个图的补图。

（2）输入有向图的各边所关联的顶点对，确定每个顶点的出度和入度。

二、　编写一个程序，要求于无向图和有向图都能做到：输入图的邻接矩阵和正整数n，求长度为n的链和圈。

三、模拟判断一个程序中是否存在递归的函数，若存在，如何消除递归。

四、输入图的边，确定这是否为连通图。

（1）若不是连通图，则确定连通分图的个数；

（2）若是连通图，判断是否存在割边和割点，若存在各是什么？

五、输入一个多重图各边关联的顶点对。

（1） 判断它是否存在欧拉圈，若存在，则求出一个欧拉圈；

（2）若不存在，则判断是否存在一个欧拉链，若存在则求之。

六、输入一个简单图的边列表。

（1）确定是否存在哈密尔顿圈，若存在求该哈密尔顿圈；

（2）若不存在，判断是否存在哈密尔顿链，若存在则求之。

七、自选一个算法求货郎担问题。

八、给定带权连通简单图的边及权列表，输入图中两个顶点，求两点是否可达？若可达距离为多少？并输出这条最短的链。

提示：

可以使用Dijkstra算法——迪杰斯特拉算法）

九、给定无向图的边列表，对该图进行着色，求着色数。

十、输入一个加权无向简单图的边及权列表，求最小生成树，以及这棵最迟薯棚小生成树的权。

十一、输码则入一段文章，全部用小写字母，求各字母的哈夫曼编码。

十二、要给n个人分配m个资源，输入每个人可以获得的资源情况，求最大匹配，

要求所有资源在满足尽可能手手多的人获得的情况下，全部分配出去。

---