蒟蒻在没学之前用普通bfs卡最后一个数据TLE，因此在学过之后决定写一写心得。欢迎大佬指出错误，感激不尽。（代码C++实现）

题目描述

对于题目中给到的例子：

鱼越大，鱼刺越大；鱼刺越大，肉越少；肉越少，鱼越小；所以鱼越大，鱼越小

我们可以其看作：

如若我们将【鱼越大】【鱼刺越小】 这样的一个个论点看作一个个点，那么我们可以发现，这其实就是一张图；

那么我们的问题也就成功的转化为了：

在这张图中寻找一条由起点到终点距离最短的路径。

转换后的解题思路

我们由题可知，并不是每一个点都有终点：
以 xxxx flag 为起点的路径 必须以 xxxx !flag 作为结尾

我们可以遍历每一个点，然后以此点作为起点，通过bfs来搜索出是否存在完整路径。并把以此点为起点的完整路径的最短距离计算出来。遍历完所有的点后，然后再打印出所有起点中距离最小的那个。

解题步骤

我们将这道题分成三个步骤。
1.如何将由字符串表示的词条映射为图中的一个点
2.如何搜索
3.如何打印

① 将由字符串表示的词条映射为图中的一个点

我们可以用 unordered_map

unordered_map<A,B> 是一种哈希映射 我们可以通过 类型A来找到B 详细操作为 d【a】=b

举个例子：

unordered_map< string , int > d;
string str="YuCi 0"；
d[str]=1;

此时我们就通过 unordered_map 将 YuCi 0 映射为了 数字 1
我们遍历图的时候，想知道 YuCi 0 可以到达哪些词条，就可以直接访问 head[1]的邻接表查看。
同时，我们要对映射进行一个备份。
开一个结构体数组e[],e[t]就存储着映射为 数字 t 的论点的信息。
以便于后面的起点终点判断和字符串打印。

②如何搜索

我们可以遍历每一个点，然后以此点作为起点，通过bfs来搜索出是否存在完整路径。并把以此点为起点的完整路径的最短距离计算出来。
不了解的可以移步 y总的【算法基础课】-【图的bfs】。

③如何打印

遍历完所有的点时，在每次更新完路径后，将此点的前置点标记在此点处（类似于链表）
比如：dist[j]=dist[t]+1;
我们就知道j点的新路径是由t点发展来的。因此，node[j].prev[a]=t;
（prev后面的数组[a]表示的是他是以点a为起点的路径）
然后在打印时，每次递归其前置点，打印此点词条，然后继续递归，直至前置点与起始点重合。

让我们看看代码是如何实现的。

C++

#include<bits/stdc++.h>

using namespace std;


const int N=1005*2;//有向图，一条推论由两个点（两个论点）和一条边形成，因此N条推论实际最多有2000个点。

struct Node     //标准的邻接表存贮图（我习惯了结构体写链表，见谅sry）
{
    int next;
    int point;
};
Node node[N];
int head[N],tot;

void insert(int x,int y)//图的存储函数
{
    node[++tot].next=head[x];
    head[x]=tot;
    node[tot].point=y;
}

struct Entry    //这个结构体就是我们上面说的结构体数组e[],用于存储着映射为 数字 t 的字符串的信息。
{
    string entry;   //论点的字符串
    string flag;    //论点后面的0/1
    int prev[N];//用于后面标记前置点序号
};
Entry e[N];

unordered_map <string , int> d; //推论与数字之间完成映射的重要工具
int cnt;

int n;
int ed[N];//ed[a]＝b 以第a个点为起点的路径的结尾是点b

int dist[N];//bfs中用于存储步数的数组

int bfs(int a)  //bfs宽搜函数
{
    queue<int> q;
    q.push(a);

    memset(dist,-1,sizeof dist);

    dist[a]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=head[t];i!=-1;i=node[i].next)
        {
            int j=node[i].point;
            if(dist[j]!=-1) continue;//dist【】=-1意味着未被遍历过
            dist[j]=dist[t]+1;
            e[j].prev[a]=t;//记录第a个点为起点的每个点的前置点
            if(e[a].entry==e[j].entry && e[a].flag!= e[j].flag)
            {
                ed[a]=j;
                return dist[j];
            }
            q.push(j);
        }
    }
    return 0x3f3f3f3f;//如果没有找到完整路径就返回一个很大的数，
    //意味着无穷远，无法到达，计算最小距离的时候自然就不需要顾及它了
}

void printt( int t,int sta,int ed )//t：当前层 sta：起始层 ed：终点层
{
    if(t!=sta)
        printt(e[t].prev[sta],sta,ed);
    if(t!=sta && t!=ed) //因为输出是 a—>b;b—>c;c—>d;这样的模式,
    //因此不在起始层和终点层的论点要打印两次，
    //一次作为一个推论的终点被引出，一次作为一个推论的起点引出下一个论点。
    {
        cout<<e[t].entry<<' ';
        cout<<e[t].flag<<' ';
    }
    cout<<e[t].entry<<' ';
    cout<<e[t].flag<<' ';

}
int main()
{
    memset(head,-1,sizeof head);//初始化图
    cin>>n;
    while(n--)
    {
        string s1,s2,s3,s4;
        cin>>s1>>s2>>s3>>s4;
        string s5=s1+' '+s2;
        string s6=s3+' '+s4;
        if(!d.count(s5))    //d.count()用于勘察此论点是否出现过。

        {       //如果没有出现过
            d[s5]=++cnt;    //为他注册一个新的映射
            e[cnt].entry=s1;//存贮新论点的信息
            e[cnt].flag=s2;
        }
        if(!d.count(s6))
        {
            d[s6]=++cnt;
            e[cnt].entry=s3;
            e[cnt].flag=s4;
        }
        insert(d[s5],d[s6]);
    }

    int mmin=INT_MAX,mmin_bh=-1;
    for(int i=1;i<=cnt;i++)
    {
        int dis=bfs(i);
        if(mmin>dis)    //比较一下以映射为数字i的论点为起点的映射到达终点的距离
                        //确保mmin中存贮的是最小的距离
                        //mmin_bh用于存储最短路径所在起点的数字
            {
                mmin=dis;
                mmin_bh=i;
            }
    }
    printt(ed[mmin_bh],mmin_bh,ed[mmin_bh]);
    cout<<"= "<<e[mmin_bh].entry<<' '<<e[mmin_bh].flag<<' '<<e[ed[mmin_bh]].entry<<' '<<e[ed[mmin_bh]].flag<<endl;
    return 0;
}