#include<iostream>
#include<iomanip>
#include<string>
#include<fstream>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<array>
#include<vector>
#include<map>
#include<queue>
using namespace std;
class MapLinknode {
public:
    int name;
    MapLinknode* next=nullptr;
};
typedef MapLinknode* MapLinkPoint;
class MapPlacenode
{
public:
    int name;
    MapLinkPoint first=nullptr;
};
typedef MapPlacenode* MapPlacePoint;
class MapGraph {
public:
    int num;
    MapPlacePoint* data;
    MapGraph(int num)
    {
        this->num = num;
        this->data = new MapPlacePoint[num];
        for (int i = 0; i < num; i++)
        {
            (this->data)[i] = new MapPlacenode();
        }
        for (int i = 0; i < num; i++)
        {
            int itname;
            cin >> itname;
            (this->data)[i]->name = itname;
            int number;
            cin >> number;
   
            for (int j = 0; j < number; j++)
            {
                int pointname;
                cin >> pointname;
                MapLinkPoint nLp = new MapLinknode();
                nLp->name = pointname;
                MapLinkPoint pre = (this->data)[i]->first;;
                (this->data)[i]->first = nLp;
                nLp->next = pre; //头插法
            }
        }
    }
    void ShowMap()
    {
        for (int i = 0; i < num; i++)
        {
            cout << data[i]->name <<"  ";
            MapLinkPoint now = data[i]->first;
            while (now)
            {
                cout << now->name;
                now = now->next;
            }
            cout << endl;
        }
    }
    void BFS()
    {
        bool* flag = new bool[num];
        for (int i = 0; i < num; i++)
        {
            flag[i] = false;
        }
        for (int i = 0; i < num; i++)
        {

            if (flag[i] == false)
            {
                BFS_Core(i, flag);
            }
        }
    }
    void BFS_Core(int i, bool* flag)
    {
        queue<int> newqueue;
        newqueue.push(i);
        while (!newqueue.empty()) //我们就用 0 开头的图
        {
            int p = newqueue.front();
            flag[p] = true;
            newqueue.pop();
            cout << p << endl;
            MapLinkPoint now = data[p]->first; //这样应该也没什么问题
            while (now)
            {
                if (flag[now->name] == false)
                {
                    newqueue.push(now->name);
                    flag[now->name] = true;
                }
                now = now->next;
            }
        }
    }
    void DFS()
    {
        bool* flag = new bool[num];
        for (int i = 0; i < num; i++)
        {
            flag[i] = false;
        }
        for (int i = 0; i < num; i++)
        {
            if (flag[i] == false)
            {
               No_DiGuiDFS(i,flag);
            }
        }
    }
    void DFS_Core(int i, bool* flag)
    {
        flag[i] = true;
        cout << i << endl;
        MapLinkPoint now = data[i]->first;
        while (now)
        {
            if (flag[now->name] == false)
            {
                DFS_Core(now->name, flag);
            }
            now = now->next;
        }
    }
    void DFS_Core2(int i,int j, int* a, int length,bool* flag)
    {
        flag[i] = true;
        a[length] = i;
        //找到了一条路径
        for (int p = 0; p <= length; p++)
        {
            cout << a[p] << " ";
        }
        cout << "---------------------------------------------" << endl;
        if (i == j)
        {
            //输出数组内全部内容
            for (int p = 0; p <= length; p++)
            {
                cout << a[p] << " ";
            }
            cout << endl;
            return;
        }
        MapLinkPoint now = data[i]->first;
        while (now)
        {
            if (flag[now->name] == false)
            {
                DFS_Core2(now->name, j, a, length+1, flag);
                flag[now->name] = false;
            }
            now = now->next;
        }
      
    }
    void No_DiGuiDFS(int i,bool* flag)
    {
        //必然依托栈实现
        stack<int> newstack;
        newstack.push(i);
        flag[i] = true;
        cout << i;
        while (!newstack.empty())
        {
            int nownumber = newstack.top();
            MapLinkPoint nowpoint = data[nownumber]->first;
            bool count = false;
            while (nowpoint)
            {
                if (nowpoint != nullptr && flag[nowpoint->name] == false) //这里这个点表示没有访问过
                {
                    count = true;
                    newstack.push(nowpoint->name);
                    cout << nowpoint->name;
                    flag[nowpoint->name] = true;
                    break;
                }
                nowpoint = nowpoint->next;
            }
            if (count == false)
            {
                newstack.pop();
            }
        }
    }
};
void ISorNotTree(MapGraph mg)
{
    bool* flag = new bool[mg.num];
    for (int i = 0; i < mg.num; i++)
    {
        flag[i] = false;
    }
   mg.DFS_Core(0,flag);
   for (int i = 0; i < mg.num; i++)
   {
       if (flag[i] == false)
       {
           cout << "此图不是树 因为不连通" << endl;
           return;
       }
   }
   int count = 0;
   for (int i = 0; i < mg.num; i++)
   {
       MapLinkPoint now = mg.data[i]->first;
       while (now)
       {
           count++;
           now = now->next;
       }
   }
   cout << count;
   if (count != mg.num * 2-2)
   {
       cout << "此图不是树，因为枝杈太多且联通一定有环" << endl;
   }
   else
   {
       cout << "这个图是树" << endl;
   }
}
int main()
{
    MapGraph newGraph(8);
    newGraph.ShowMap();
    cout << "---------------------------------" << endl;
    newGraph.BFS();
    cout << "---------------------------------" << endl;
    newGraph.DFS();
    cout << endl;
    cout << "---------------------------------" << endl;
    ISorNotTree(newGraph);
    int* a = new int[newGraph.num]{0};
    bool* flag = new bool[newGraph.num];
    for (int i = 0; i < newGraph.num; i++)
    {
        flag[i] = false;
    }
    newGraph.DFS_Core2(0, 6, a, 0, flag);
    /*
   0 2 1 4
1 3 0 7 2
2 3 1 3 5
3 2 2 6
4 2 0 5
5 3 2 4 6
6 2 3 5
7 1 1

    */

}

//输入内容为 AB#DG##H##CEI##JK##L##F##
//前序为ABDGHCEIJKLF
//中序为BGDHAIEKJLCF
//后序为GHDBIKLJEFCA
//层序为ABCDEFGHIJKL
//测试样例2
////输入为 AB#D##CE#G##FH###
 //前序输出为 ABDCEGFH
//中序输出为BDAEGCHF
//后序输出为DBGEHFCA 
//图的话就自己画吧