刚开始学习C语言,准备在做hiho的题目的过程中来学习,在此进行记录,如果代码中有错误或者不当的地方还请指正。
描述
大家好,我是小Hi和小Ho的小伙伴Nettle,从这个星期开始由我来完成我们的Weekly。
新年回家,又到了一年一度大龄剩男剩女的相亲时间。Nettle去姑姑家玩的时候看到了一张姑姑写的相亲情况表,上面都是姑姑介绍相亲的剩男剩女们。每行有2个名字,表示这两个人有一场相亲。由于姑姑年龄比较大了记性不是太好,加上相亲的人很多,所以姑姑一时也想不起来其中有些人的性别。因此她拜托我检查一下相亲表里面有没有错误的记录,即是否把两个同性安排了相亲。
OK,让我们愉快的暴力搜索吧!
才怪咧。
对于拿到的相亲情况表,我们不妨将其转化成一个图。将每一个人作为一个点(编号1..N),若两个人之间有一场相亲,则在对应的点之间连接一条无向边。(如下图)
因为相亲总是在男女之间进行的,所以每一条边的两边对应的人总是不同性别。假设表示男性的节点染成白色,女性的节点染色黑色。对于得到的无向图来说,即每一条边的两端一定是一白一黑。如果存在一条边两端同为白色或者黑色,则表示这一条边所表示的记录有误。
由于我们并不知道每个人的性别,我们的问题就转化为判定是否存在一个合理的染色方案,使得我们所建立的无向图满足每一条边两端的顶点颜色都不相同。
那么,我们不妨将所有的点初始为未染色的状态。随机选择一个点,将其染成白色。再以它为起点,将所有相邻的点染成黑色。再以这些黑色的点为起点,将所有与其相邻未染色的点染成白色。不断重复直到整个图都染色完成。(如下图)
在染色的过程中,我们应该怎样发现错误的记录呢?相信你一定发现了吧。对于一个已经染色的点,如果存在一个与它相邻的已染色点和它的颜色相同,那么就一定存在一条错误的记录。(如上图的4,5节点)
到此我们就得到了整个图的算法:
- 选取一个未染色的点u进行染色
- 遍历u的相邻节点v:若v未染色,则染色成与u不同的颜色,并对v重复第2步;若v已经染色,如果 u和v颜色相同,判定不可行退出遍历。
- 若所有节点均已染色,则判定可行。
接下来就动手写写吧!
输入
第1行:1个正整数T(1≤T≤10)
接下来T组数据,每组数据按照以下格式给出:
第1行:2个正整数N,M(1≤N≤10,000,1≤M≤40,000)
第2..M+1行:每行两个整数u,v表示u和v之间有一条边
输出
第1..T行:第i行表示第i组数据是否有误。如果是正确的数据输出”Correct”,否则输出”Wrong”
- 样例输入
-
2
5 5
1 2
1 3
3 4
5 2
1 5
5 5
1 2
1 3
3 4
5 2
3 5
样例输出
Wrong
Correct
解决思路
使用一个结构体记录一个人的所有信息{性别,约会数量,约会对象},其中约会对象通过指向指针数组的指针来实现。
这样的结构体可以在读取数据的过程中把所有的信息全部存储下来。
在进行性别判断时有一种情况需要考虑,可能存在几个人是单独成一组的,就是说这几个是独立于其他人的他们只在
他们自己内部之间有约会,而不与其他人有约会。这时如果你一开始选取的点的逻辑中不包含他们,那么按照题目提示的
方法是无法考虑到他们的。我采用的方法是,在第一个循环中为每个没有性别的人都赋予性别,但是赋予性别后用递推把
所有与他存在逻辑关系的人的性别全部确定。这样做的结果是如果他们所有人都互相之间存在逻辑关联的话,当我给第一
个人一个性别并递推他的关系时就给所有人都赋予了性别,当存在前面所说的特殊情况时,我们的第一层循环也会找到这
些逻辑上独立的人,将他们的关系递推出来。
但是现在在我编出的程序中存在问题,我的运行结果是RE,我暂时还没有找到错误的地方,希望看到的人给以帮助。
#include<stdio.h>
#define OPPSEX(sex) sex==1?2:1 typedef struct PEOPLE
{
int Sex; //sex 无性别0,男性1,女性2;
int PDateNum; //约会数量
struct PEOPLE **DataToOther; //指向约会对象的数组的指针
}people; //正确返回0,错误返回1
int JudgeDateROW(people *Group,int PeoNum,int DateNum)
{
int i;
for(i=;i<PeoNum;i++)
{
if(Group[i+].Sex==)
{
Group[i+].Sex=;
if(derive_others(&Group[i+])==)
return ;
}
}
return ;
}
//正确返回0,错误返回1
int derive_others(people *Person)
{
int i;
for(i=;i<Person->PDateNum;i++)
{
if(Person->DataToOther[i]->Sex==)
Person->DataToOther[i]->Sex=OPPSEX(Person->Sex);
else
{
if(Person->DataToOther[i]->Sex==Person->Sex)
return ;
else
return ;
}
if(derive_others(Person->DataToOther[i])==)
return ;
}
return ;
} int main(void)
{
int PeoNum,DateNum,GroupNum;
int i,j,k;
char *Answer[]={"Correct","Wrong"};
//获得数据量
scanf("%d",&GroupNum);
int AnswerNum[GroupNum];
//获取每组的数据,并得到分析结果
for(i=;i<GroupNum;i++)
{
int person1,person2;
//获取人数和约会数
scanf("%d %d",&PeoNum,&DateNum);
people *Group;
//为这组人分配人数加一个人的内存,第零个忽略掉
Group=calloc(sizeof(people),PeoNum+);
size_t PDateSize=sizeof(people*)*;
//先为每个人分配5个约会的指针内存
for(j=;j<=PeoNum;j++)
Group[j].DataToOther=(people**)calloc(sizeof(people*),);
//读取每组数据,并生成二分图
for(j=;j<DateNum;j++)
{
scanf("%d %d",&person1,&person2);
//判断是否需要分配更多的内存给约会指针
if((Group[person1].PDateNum+)%==)
Group[person1].DataToOther=(people**)realloc(Group[person1].DataToOther,\
sizeof(people*)*(Group[person1].PDateNum+));
if((Group[person2].PDateNum+)%==)
Group[person2].DataToOther=(people**)realloc(Group[person2].DataToOther,\
sizeof(people*)*(Group[person2].PDateNum+));
//记录互相的约会,并将约会数量加一
*(Group[person1].DataToOther+Group[person1].PDateNum)=&Group[person2];
Group[person2].DataToOther[Group[person2].PDateNum]=&Group[person1];
Group[person1].PDateNum++;
Group[person2].PDateNum++;
}
//判断分组是否正确
AnswerNum[i]=JudgeDateROW(Group,PeoNum,DateNum);
//释放本组分配的内存
for(j=;j<=PeoNum;j++)
free(*Group[j].DataToOther);
free(Group);
}
//输出分析结果
for(i=;i<GroupNum;i++)
printf("%s\n",Answer[AnswerNum[i]]);
return ;
}