小小编程题（C语言）

来源：百度知道 编辑：UC知道 时间：2024/06/22 06:33:12
求出n叉路口需要几盏信号灯来管理交通。可以通行的方向及个数和不能同时通行的两个方向及个数均由用户输入。最后输出信号灯的数量以及每个信号灯管理的可以同时通行方向。
样例输入：
13 // 可以通向的方向的个数
AB AC AD BA BC BD DA DB DC EA EB EC ED
// 以字符串方式输入
20 // 不能同时通行的两个方向的个数
AB DA
AB EA
AB BC
AB BD
AC EB
AC DA
AC EA
AC DB
AC BD
AD EA
AD EB
AD EC
BC EB
BC DB
BD DA
BD EC
BD EB
DA EB
DA EC
DB EC
样例输出：
4
1 AB AC AD BA DC ED
2 BC BD EA
3 DA DB
4 EB EC
蛮急的，请大家说清楚一点 帮忙写一下吧……

类似于曾经学过离散数学的染色问题。

首先用数组或结构记录下“可通行的方向”、“互斥的方向”，然后按以下逻辑找：
如例题所说
第一个灯控制AB方向，然后依次从“可通行的方向”数组里找与AB不互斥的（循环），归纳在第一个灯的控制下，如题分别有AC、AD、BA；
碰到BC时，发现AB与它互斥，先暂时将BC归在第二个灯的控制下，继续找AB的“同类”；
碰到BD时，发现与AB互斥，接着判断与BC互斥否？（循环即可）不互斥则归为一类，否则开的三个信号灯。
如此循环下去即可。

有必要的话楼主可以问我要代码，就不在这贴了。

咯咯
排列组合问题
将
数学思想
转化为
编程代码
即可
//以下为程序代码 参考
#include<stdio.h>
#include <string.h>
#include <malloc.h>
void main()
{
int front,rear,temp,n,m,i,j,k,l,group,pre,result[100],newer[100],r[100][100]={0};/*front为队列当前元素在队列中的序号,rear为队尾元素在队列中的序号,temp为当前 元素在direction中的序号,group为组号,pre为前一出列元素在direction中的序号。 */
char **direction,*p1,*p2;//direction为方向集合。
printf("请输入可以通行的方向的个数：\n");
scanf("%d",&n);
print