9.9华为机试第二题

int dfs(unordered_map<int, vector<int>>& map, int i, vector<int>& path,vector<bool>& isused,vector<bool>& mused)
{
    if (isused[i])
    {
        path.push_back(i);
        return i;
    }
    if (mused[i])
        return -1;

    mused[i] = true;
    isused[i] = true;
    path.push_back(i);
    int ret = -1;
    if (map.count(i))
    {

        for (auto& p : map[i])
        {
            ret = dfs(map, p, path, isused, mused);
            if (ret != -1)
            {
                
                return ret;
            }
        }

    }
    path.pop_back();
    isused[i] = false;
    return ret;
}

int main()
{
    int  n;
    while (cin >> n)
    {
        unordered_map<int, vector<int>> map;

        for (int i = 0; i < n; ++i)
        {        
            int m;
            cin >> m;

            int x;
            cin >> x;
            for (int i = 1; i < m; ++i)
            {
                int y;
                cin >> y;
                map[x].emplace_back(y);
            }
        }

        vector<bool> isused(10000, false);
        vector<bool> mused(10000, false);
        for (auto& mp : map)
        {
            vector<int> path;
            int res = dfs(map, mp.first, path, isused, mused);
            if (res != -1)
            {
                int i = 0;
                for (; i < path.size(); ++i)
                {
                    if (path[i] == res)
                    {
                        break;
                    }
                }

                for (int j = i; j < path.size(); ++j)
                {
                    cout << path[j] << " ";
                }
                cout << endl;
                break;
            }
        }
    }

    system("pause");
    return 0;
}
#华为机试#