题目描述

同学们应该学会多交一些好朋友。朋友关系是相互的，A 是 B 的好朋友，则 B 也是 A 的好朋友。朋友关系是不传递的，A 是 B 的好朋友，B 是 C 的好朋友，但 A 和 C 不一定是好朋友。现在给出某小学部分同学之间的朋友关系，请编程统计朋友最多的人有多少个好朋友。 

 

输入

输入共m+1行。
第1行是两个整数n和m，分别表示同学总人数和朋友关系对数。
第2行到第m+1行，描述了m对朋友关系。每行两个用单个空格隔开的同学姓名。
每个人的姓名仅由小写字母组成，且1≤姓名的长度≤10。

 

 

输出

输出共 1 行。  
一个整数，表示朋友最多的人有多少个好朋友。

分析：

这个题目是我的一个比赛题目，没有做出来，后来听学长讲的，才有了点思路。

其实这个题目的关键就是判断，这个字符串出现过没有，并且成对出现的字符串有什么关系。

学长的思路很好，如果不是字符串，而是一堆数字，就可以用二维数组表示，比如说a[1][2] a[1][3],这样我们把1 2 1 3标记为1，然后把第一行的加起来，就是数字1的朋友。但是有可能数字一 会是别人的朋友，比如说 3 1，这样1和3也是朋友，所以1的朋友数为，1这一行的和+1这一列的和。但是2 1 1 2重了，所以应该把其中一个标为0。这样做一个判断就好。

问题的关键在于 怎么把字符串转为下标。

写一个函数 pos函数：

char s[200][50];
int cnt=1;
int pos(char x[])
{
    for(int i=0;i<cnt;i++)
        if(strcmp(s[i],x)==0)
            return i;
    strcpy(s[cnt++],x);
            return cnt-1;
}

用到了字符串里面的函数，初始cnt=0，直接把一个字符串复制到二维数组s[][]中，以此推，下一次如果出现一样的，那么这个字符串代表的数字，否则放到下一个一维数组中，并且设为一个新的下标。这样就把每一个字符串都有了一个数字与其对应。

每次输入一对，都把这一对转化成对应的数字，比如说 a c  c b 代表的矩阵就是

 0 1 0
 0 0 1
 0 0 0
这个矩阵的意思：第一个输进的数是a，第二个输进去的数是c，第三个为b，他们分别对应 1 2 3，所以从矩阵可以看出，1 2 是朋友。2 3也是朋友。所以最多朋友是1.

具体实现代码如下：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
char s[200][50];
int cnt=1;
bool cmp(int a,int b)
{
    return a>b;
}
int pos(char x[])
{
    for(int i=0;i<cnt;i++)
        if(strcmp(s[i],x)==0)
            return i;
    strcpy(s[cnt++],x);
            return cnt-1;
}
int main()
{
    int m,n;
    int a[200][200];
    char s1[500],s2[500];
    int ans[2000];
    int x,y,z;
    int vis[200][200];
    int num=1;
    int sum[200];
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s%s",s1,s2);
        x=pos(s1);
        y=pos(s2);
        if(!vis[y][x])
            vis[x][y]=1;
    }
    /*for(int i=1;i<=cnt-1;i++)
    {
        for(int k=1;k<=m;k++)
            printf("%2d",vis[i][k]);
        printf("\n");
    }*/
  for(int i=1;i<=m;i++)
    {
        for(int k=1;k<=m;k++)
        {
            sum[i]+=vis[i][k];
            sum[i]+=vis[k][i];
        }
    }
    sort(sum+1,sum+1+cnt,cmp);
    printf("%d",sum[1]);
    return 0;
}

简单代码，大神勿喷。