问题1506蓝桥杯 算法提高卡勒沃夫之弱水三千 题解

这个题目表面上是一个字符串排序问题  但处理起来有些复杂

因为题目只是告诉了 两两字符串之间的对应关系 

所以本题的处理策略是  找出那个第一任女友 第一任女友有个特点就是她只出现在左边

找出第一任女友的前提是把所有的字符串输入到mm数组中 并用link数组记录输入的每一行的两个女孩在mm数组中的位置

link[i][0] link[i][1]分别是记录在左边和右边的女孩  用in[link[i][1]]++ 然后找出in[i]==0的那个i 就是第一任女友 
因为她从未在右边出现过   之后利用fun(i)  fun函数的作用是按女孩出现的先后顺序给这些女孩赋值  mm[i]是第一个
出现的  所以遍历link[i][0] 找出第一任女友出现的每一行  给每一行的右边的女孩y 赋上 max(length[x] ,length[x]+1）
的值 之后fun（y) 找出每一个比y大的人 进行赋值  最终结束循环后  所有的字符串都被赋上了 正确的值



就像是一个横向的二叉树一样 （可能比喻不是很贴切）
但这是一个很棒的排序思路
实现起来可能比较复杂  所以需要细心 一些 耐心一些 
本人水平不足  欢迎大家批评指正

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std; 
char mm[105][15];  
char s1[15],s2[15];  
int link[105][2];  
int length[105]={0};  
int in[105];  
int N;  
struct girl 
{  
    char name[15];  
    int num;  
}g[105];  //记录最后的结果 包括女孩的名字 及女孩成为女朋友的先后顺序 
void fun(int x) //给每个字符串按照先后顺序赋上相应的值 
{  
    int i,y;  
    for(i=0;i<N;i++)  
        if(link[i][0]==x)  //在左边找到了该字符串 
        {  
            y=link[i][1];  //y是它的右边字符串 
            length[ y ]=length[x]+1>=length[y]?length[x]+1:length[y];  //右边字符串的值为
//max(左边字符串的值+1，本身字符串的值） 
            fun(y);  //接着寻找当它作为左边字符串时的情况  
        }  
}  
int comp(girl a, girl b)  
{  
    return a.num<b.num ;//按从小到大排序 
}  
int main()  
{  
    int i,j,T,n,f,x,y;   
    cin>>T;//测试数据的组数 
    while(T--)  
    {  
        memset(mm,0,sizeof(mm));//该数组保存输入的女孩的名字  同时初始化所有的数组  
        memset(link,0,sizeof(link)); //该数组记录每行输入的两个女孩的名字在mm数组中的位置 
        memset(in,0,sizeof(in));  //该数组记录女孩的名字在右边出现过的次数 
        memset(length,0,sizeof(length));  //按女孩出现的先后顺序给女孩赋值 
        cin>>N; //每组测试数据下的需要比较的行数 即两个MM之间进行比较 
        n=0;  //mm数组中元素的个数 也即是mm的个数 
        for(i=0;i<N;i++)  
        {  
            scanf("%s%s",s1,s2);  //输入两个MM的名字 
            f=0;  
            for(j=0;j<n;j++)  
                if(strcmp(s1,mm[j])==0)  //如果mm数组里面已经有了输入的第一个MM的名字  那么
                用 x记录下这个MM名字的位置 
                {  
                    f=1;  
                    break;  
                }  
            if(f==1)  
                x=j;  //x记录mm名字的位置 
            else  //如果mm数组里面没有即将输入的第一个MM的名字  则将该字符串输入到mm数组中  
            //同时记录该字符串的位置 
            {  
                strcpy(mm[n++],s1);  
                x=n-1;  //记录字符串的位置 
            }  
            f=0;  
            for(j=0;j<n;j++)  //同理记录第二个MM的名字 如果mm数组中已经有了该MM的名字  
            //记录该字符串的位置 
                if(strcmp(s2,mm[j])==0)  
                {  
                    f=1;  
                    break;  
                }  
            if(f==1)  
                y=j;  //记录第二个mm名字的位置 
            else  
            {  
                strcpy(mm[n++],s2);  //否则将该MM的名字输入到mm数组中去 
                y=n-1;  
            }  
            link[i][0]=x;  //记录下每一行输入的两个MM的名字在数组中的位置，i代表行数 
            link[i][1]=y;  //每一行的字符串S1，s2在mm数组中的位置 
        }  
        for(i=0;i<N;i++)  
            in[link[i][1]]++;  //以在右边的小姐姐在mm数组中的位置 作为in数组中的下标   
            //来保存该MM在右边出现的次数 
        for(i=0;i<n;i++)  
            if(in[i]==0)  //找到第一个没有出现在右边的字符串（即为第一任女友） 记录下它的下标 
                break;  
        fun(i);  //将该下标作为函数的实参 
        for(i=0;i<n;i++)  
        {  
            strcpy(g[i].name,mm[i]);  //将mm数组以及length数组复制到g[i]数组中 
            g[i].num=length[i];  
        }         
        sort(g,g+n,comp);  //对数组元素以num的值进行从小到大的排序 
        for(i=0;i<n;i++)  
        {  
            printf("%s",g[i].name);  //输出女朋友出现的先后次序 
            if(i==n-1)  
                printf("\n");  
            else  
                printf(" ");  
        }      
    }  
    return 0;  
}