美团笔试题 - 小团的旅行线路

题目：小团的旅行线路

时间限制： 1000MS

内存限制： 65536KB

题目描述

小团是一个旅游爱好者，快要过春节了，他想统计一下，在过去的一年中他进行过几次旅行，于是他打开了美团app的订单记录，记录显示了他的购买车票的记录。记录是按时间顺序给出的，已知一次旅行的线路一定是一个闭环，即起点和终点是同一个地点。因此当每找到一段闭合的行程，即认为完成了一次旅行。数据保证不会出现不在闭环路径中的数据。请你在小团的购票记录中统计出他全年共进行了多少次旅行？

输入描述

输入第一行包含一个正整数n，表示小团的购票记录数量。(1<=n<=10000)

接下来有n行，每行是两个长度不超过10的仅由小写字母组成的字符串S_a，S_b，表示购买了一张从S_a到S_b的车票。

输出描述

输出仅包含一个整数，表示小团的旅行次数。

样例输入

6
beijing nanjing
nanjing guangzhou
guangzhou shanghai
shanghai beijing
fuzhou beijing
beijing fuzhou

样例输出

2

解题思路

需要注意的是，题目指明了两个重要信息，第一，记录是按时间顺序给出的；第二，不存在不在闭环中的数据。

也就是说从一个地方出发，总会在后续某一个行程中回到这个地方，那么问题就好解决了，只需要记录小团出发的城市，并且每添加一条数据我们就可以判断当前行程的到达城市是否之前的某个出发城市，如果是那么就找到了一个闭环，将旅行次数+1即可。

源码

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int times = 0;  // 次数
    int n;  // 数量
    cin >> n;
    vector<string> vec;  // 出发城市列表
    for (int i = 0; i < n; i++) {
        string str1, str2;
        cin >> str1 >> str2;
        vec.push_back(str1);  //添加当前出发地到出发城市列表
        for (int j = 0; j < vec.size(); j++) {
            // 遍历出发城市列表判断当前行程的到大城市是否是之前的出发城市
            // 如果是，则找到一个闭环，旅行次数+1，并将该城市从列表中删除
            if (vec[j] == str2) {
                vec.erase(vec.begin() + j);
                times++;
            }
        }
    }
    cout << times << endl;
    return 0;
}