解题思路

这道题目要求我们找到两个校友之间的最短路径（最少中间人数量），可以建模为无权无向图的最短路径问题，适合使用 BFS（广度优先搜索） 来求解。

关键点：

1. 图的存储：使用邻接表（Adjacency List）存储每个节点的邻居，因为校友数量$N$可能很大（$N \leq 10^5$），邻接矩阵会超出内存限制。
2. BFS搜索：从起点$c_1$出发，逐层遍历，直到找到目标$c_2$，记录路径长度。
3. 中间人数量计算：最短路径长度$-1$（因为题目要求的是“中间人”的数量，不包括起点和终点）。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100001
#define INF 0x3f3f3f3f
struct ArcNode{
    int to;
    int weigh;
    struct ArcNode *next;
};
struct ArcNode *listb[MAX];
 
int a,b,e,s,n,list[MAX*400],dist[MAX]={0},time[MAX]={0}; //time[]纪录到底此点是走了多少个站点
 
void SPFA(int v0)
{
    int u,v;
    struct ArcNode *temp;
    s=e=0;
    list[e++]=v0;
    dist[v0]=1;
    time[v0]=0;
    while(e!=s)
    {
        u=list[s++];
        dist[u]=0;
        temp=listb[u];
        while(temp!=NULL)  //访问邻接链表
        {
            v=temp->to;
            if(dist[v]!=1)  //***如果不在队列中则入队，没有此判断会 WA
            {
                list[e++]=v;
                time[v]=time[u]+1;  //***time[v]是上点走的站点总数再 +1
                dist[v]=1;
            }
            if(v==b)
            {
                return ;  //第一次到达 b 就立刻退出
            }
            temp=temp->next;
        }
    }
}
 
int main()
{
    int i,j,m;
    struct ArcNode *temp;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&a,&m);
        for(j=0;j<m;j++)
        {
            scanf("%d",&b);
            temp=(struct ArcNode*)malloc(sizeof(struct ArcNode));  //构建邻接链表
            temp->to=b;
            temp->weigh=1;
            temp->next=NULL;
            if(listb[a]==NULL)
                listb[a]=temp;
            else
            {
                temp->next=listb[a];
                listb[a]=temp;
            }
        }
    }
    scanf("%d%d",&a,&b);
    SPFA(a);  //从a点开始 SPFA
    printf("%d %d %d\n",a,b,time[b]-1);
    return 0;
}