首页 > 美团2020年8月15日测开笔试第二题
头像
会哥哥
编辑于 2020-08-20 11:04
+ 关注

美团2020年8月15日测开笔试第二题

//美团第二题
//旅行问题
#include <iostream>
#include <vector>
#include<set>
#include<unordered_map>
#include<string>
using namespace std;
class MyClass{
    public:
    vector<int> v;
	void addnew(){
        int n;
        cin>>n;
        string a,b;
        unordered_map<string,int> map;
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            cin>>a>>b;
            if(!map.count(a))
            {
            	map[a]=cnt;
            	v.push_back(cnt);
            	cnt++;
			}
			if(!map.count(b))
			{
				map[b]=cnt;
				v.push_back(cnt);
				cnt++;
			}
			this->un(map[a],map[b]);
        }
    }
    int sizes()
    {
    	set<int> set;
    	for(int num:v)
    	{
    		set.insert(num);
		}
		return set.size();
	}
	int find(int a)
	{
		if(v[a]!=a)
		return find(v[a]);
		return a;
	}
	void un(int a,int b)
	{
		int f1=find(a);
		int f2=find(b);
		if(f1!=f2)
		{
			v[f2]=f1;
		}
	}
	bool isCon(int a,int b)
	{
		return find(a)==find(b);
	}
};
int main()
{
	MyClass my;
	my.addnew();
	cout<<my.sizes()<<endl;                                       
    return 0;
}
欢迎在下面补充题目信息

更多模拟面试

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐