首页 > 试题广场 >

小团的旅行线路

[编程题]小团的旅行线路

热度指数：1918 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

请你在小团的购票记录中统计出他全年共进行了多少次旅行？

数据范围： $1 \le n \le 10000$ ， $1 \le len(S_a) ,len(S_b)\le10\$

进阶：时间复杂度 $O(n)\$ ,空间复杂度 $O(n)\$

输入描述:

输入第一行包含一个正整数n，表示小团的购票记录数量。(1<=n<=10000)
接下来有n行，每行是两个长度不超过10的仅由小写字母组成的字符串S_a S_b，表示购买了一张从S_a到S_b的车票。

输出描述:

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

示例1

输入

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

输出

算法知识视频讲解

znn

n = int(input())
dic = dict()
res = 0
for _ in range(n):
    s_a,s_b = [str(x) for x in raw_input().strip().split()]
    if s_a == s_b:
        res += 1
        continue
    if s_b in dic:
        res +=1
        tmp = s_b
        while tmp!= s_a:
            a = dic[tmp]
            del dic[tmp]
            tmp = a
    else:
        dic[s_a] = s_b
print(res)

有个点是：还有车票原点和终点是同一个点的情况。。。

发表于 2022-03-10 12:57:07 回复(0)

坚持就是胜利的江小鱼

import java.util.Scanner;

public class Main 
{
	public static void main(String[] args)
  {
	Scanner sc=new Scanner(System.in);
	int n=sc.nextInt();
	String[][] nums=new String[n][2];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<2;j++)
		{
			nums[i][j]=sc.next();
		}
	}
	int count=0;
	int k=0;
	for(int i=0;i<n;i++)
	{
		if(nums[k][0].equals(nums[i][1]))  //只要判断头和某个尾相等就可以了
		{
			count++;
			k=i+1;
		}
		
	}
	
	System.out.println(count);
  }
}

发表于 2021-04-04 20:49:43 回复(3)

pein531

初始化起点为空，只要在遍历的过程中做两个判断就可以了：

(1) 如果起点为空，就赋值为S_a。

(2) 如果起点等于S_b了，那就表示找到了一段闭合的行程，旅游次数+1，起点重新变为空。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int count = 0;
        String[] pos;
        String start = "";
        for(int i = 0; i < n; i++){
            pos = br.readLine().trim().split(" ");
            if(start.equals("")){
                // 起点
                start = pos[0];
            }
            if(pos[1].equals(start)){
                // 回到了起点，旅游次数+1
                count ++;
                start = "";
            }
        }
        System.out.println(count);
    }
}

发表于 2021-03-02 11:35:34 回复(3)

_叶知秋

只考虑首尾节点的话，在不按照先后顺序给出路线的情况下应该是会出错的。采用并查集的思想，判断图中的环个个数即可，可以解决无序给出路线的情况。

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main{
    // 给城市编号
    static Map<String,Integer> cities;
    // 并查集的root数组
    static int[] root;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputs = br.readLine().trim();
        int n = Integer.parseInt(inputs);
        cities = new HashMap<>();
        root = new int[n];
        for(int i=0;i<n;++i){
            root[i] = i;
        }
        // 城市编号
        int num = 0;
        // 旅行次数
        int cnt = 0;
        for(int i=0;i<n;++i){
            String[] params = br.readLine().trim().split(" ");
            if(!cities.containsKey(params[0])){
                cities.put(params[0],num++);
            }
            if(!cities.containsKey(params[1])){
                cities.put(params[1],num++);
            }
            int from = cities.get(params[0]);
            int to = cities.get(params[1]);
            // 如果一条路线上的两个城市未连通，则合并为连通分支
            // 如果已连通，说明出现了环路，完成了一次旅行
            if(!connected(from,to)){
                union(from,to);
            }else{
                cnt++;
            }
        }
        System.out.println(cnt);
    }

    public static int find(int x){
        return x == root[x]?x:(root[x] = find(root[x]));
    }

    public static void union(int x,int y){
        int rootX = find(x);
        int rootY = find(y);
        if(rootX!=rootY){
            root[rootX] = rootY;
        }
    }

    public static boolean connected(int x,int y){
        return find(x) == find(y);
    }
}

发表于 2022-03-10 15:53:26 回复(1)

三减一

#include <bits/stdc++.h>
#include <set>
#include <string>
using namespace std;

int main() {
    int n;
    cin>>n;
    string s[n][2];
    set<string> d;
    int count=0;
    for(int i=0;i<n;i++)
    {
        cin>>s[i][0]>>s[i][1];
        if(d.empty()){
            d.insert(s[i][0]);
        }
        if(d.find(s[i][1])==d.end()){
            d.insert(s[i][1]);
        }else{
            count++;
            d.clear();
        }
    }
    cout<<count;

    
}
// 64 位输出请用 printf("%lld")

发表于 2023-03-13 00:15:24 回复(0)

C/C++

_Atlantis_

#include <iostream>
#include <string>

using namespace std;
int main()
{
    int n, cnt = 0;
    cin >> n;
    string start, first, second;
    while(n--)
    {
        cin >> first >> second;
        if(first == second)    // 一定要注意出发地和目的地可能相同的情况，否则只能过一半测试用例
        {
            ++cnt;
            start.clear();
            continue;
        }
        if(start.empty())
            start = first;
        else
        {
            if(start == second)
            {
                ++cnt;
                start.clear();
            }
        }
    }
    cout << cnt;
}

发表于 2023-03-12 15:13:47 回复(0)

来自蓝星

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<string> vStr;
    int M = 0;
    for(int i = 0; i < N; i++){
        string s1,s2;
        cin>>s1>>s2;
        
        // int end = vStr.size() - 1;
        
        if(vStr.size() == 0) {
            vStr.push_back(s1);
            vStr.push_back(s2);
        } else {
            vStr.push_back(s2);
        }
        if(vStr.size()!=0 && vStr[0] == s2){
            M++;
            vStr.clear();
        } 
        
    }
    
    cout<<M<<endl;
    return 0;
}

发表于 2022-09-06 20:57:05 回复(0)

Janeispower

#include<bits/stdc++.h>

using namespace std;

int main(){
int n;
cin >> n;
stack<string> st;
int res = 1;
for(int i=0; i<n; i++){
string x, y;
cin >> x >> y;
if(i>=1){
if(x != st.top()) res++;
}
st.push(x);
st.push(y);
}
cout << res << endl;
return 0;
}

发表于 2022-08-18 15:21:03 回复(0)

JavaScript

AIcodingRobot

记录路途开始的 start，当目的地和 start 重合时，ans++，此外，出发地和目的地相同的情况也需要将ans++，该答案通过全部测试用例。

const n = parseInt(readline())
let start = ''
let ans = 0
for(let i = 0; i < n; i++) {
    const [sa, sb] = readline().split(' ')
    if(sa === sb) {
        ans++
        continue
    }
    if(start === '') {
        start = sa
        continue
    }
    if(start !== '' && sb === start) {
        start = ''
        ans++
    }
}
console.log(ans)

发表于 2022-05-23 22:10:20 回复(0)

linzetao

这。。。起始地点和到达地点一样，有这样的票？这是在车是旅行是吧，我懂了。。。

发表于 2022-05-15 18:23:09 回复(0)

不投降

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        if(num == 1) {
            System.out.println(1);
            return;
        }
        String s1,s2;
        String sa="";
        int index = 0;
        boolean flag = false;
        while(num > 0){
            s1 = sc.next();
            s2 = sc.next();
            //System.out.println(ss.length);
            if(flag == false){
                sa = s1;
            }
            if(s2.equals(sa)){
                index++;
                flag = false;
            }
            else{
                flag = true;
            }
            num--;
        }
        System.out.println(index);
    }
}

发表于 2022-03-24 22:30:56 回复(0)

Python

Ivan_2021

num = int(input())
ticket = {}
for _ in range(num):
    pair = input().split()
    if pair[0] not in ticket:
        ticket[pair[0]] = [pair[1]]
    else:
        ticket[pair[0]] += [pair[1]]
loop = set()
count = 0
while num:
    if not loop:
        start = list(ticket.keys())[0]
        loop.add(start)
        if len(ticket[start]) > 1:
            car = ticket[start].pop()
        else:
            car = ticket[start][-1]
            ticket.pop(start)
        num -= 1
    while car not in loop:
        loop.add(car)
        if len(ticket[car]) > 1:
            car = ticket[car].pop()
        else:
            wait = car
            car = ticket[car][-1]
            ticket.pop(wait)
        num -= 1
    if car == start:
        loop = set()
        count += 1
    else:
        count += 1
print(count)

记录一下小白的代码。能过。

发表于 2021-09-29 22:02:03 回复(0)

JCoder

写一个不一样的解法：并查集

每次merge之前，如果两个点的father已经一致了，答案就加一。

因为没有多余的边，所以这种方法是可行的。

#include <bits/stdc++.h>
using namespace std;

int n, fa[50005];
string a, b;
int find_fa(int x) {
    if (fa[x] != x) {
        fa[x] = find_fa(fa[x]);
    }

    return fa[x];
}

void merge_fa(int x, int y) {
    int fa_x = find_fa(x);
    int fa_y = find_fa(y);
    fa[fa_x] = fa_y;
}

int main() {
    scanf("%d", &n);
    int tot = 0;
    int ans = 0;
    map<string, int> m;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        if (m.find(a) == m.end()) {
            m[a] = tot;
            fa[m[a]] = m[a];
            tot++;
        }
        if (m.find(b) == m.end()) {
            m[b] = tot;
            fa[m[b]] = m[b];
            tot++;
        }
        if (find_fa(m[a]) == find_fa(m[b])) {
            ans++;
        }
        merge_fa(m[a], m[b]);
    }
    printf("%d\n", ans);

    return 0;
}

发表于 2021-08-18 12:22:42 回复(0)

lfx-thu

没有人觉得这个题目有问题么？测试集中有一个case，是一行输入中，起点和终点一样，请问车票的始发站和到达站能相同么？

发表于 2021-04-08 20:45:02 回复(1)

我不是最帅的

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Main_3 {
    public static void main(String[] args) throws IOException {
        Set<String> set=new HashSet<>();
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(bf.readLine().trim());
        int count=0;
        for(int i=0;i<num;i++){
            String[] s = bf.readLine().trim().split(" ");

            for(int j=0;j<2;j++){
                if(!set.contains(s[j])){
                    set.add(s[j]);
                }else {
                    set.remove(s[j]);
                    if(set.size()==0){
                        count++;
                    }
                }
            }



        }
        System.out.println(count);

    }


}

发表于 2021-03-09 14:15:57 回复(0)

不偷不抢安度因_

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    string start = "";
    int cnt = 0;
    while(n--) {
        string s_a, s_b;
        cin >> s_a >> s_b;
        if (start == "") {
            start = s_a;
        }
        if (start == s_b) {
                ++cnt;
                start = "";
            }
    }
     
    cout << cnt << endl;
    return 0;
}

发表于 2021-03-02 16:36:49 回复(0)