Timus 1837 Isenbaev's Number Solution

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <string>
#include <map>
#include <queue>
using namespace std;
map<string,int> mp;
vector<vector<int> > a(301);
vector<int> rnk(301,-1);
bitset<301> vis;
int mx=101;
queue<int> q;
int main(){
    int n;
    cin>>n;
    int x=0;
    for(int i=0;i<n;i++){
        string s1,s2,s3;
        cin>>s1>>s2>>s3;
        if(mp.find(s1)==mp.end())
            mp[s1]=x++;
        if(mp.find(s2)==mp.end())
            mp[s2]=x++;
        if(mp.find(s3)==mp.end())
            mp[s3]=x++;
        a[mp[s1]].push_back(mp[s2]);
        a[mp[s1]].push_back(mp[s3]);
        a[mp[s2]].push_back(mp[s1]);
        a[mp[s2]].push_back(mp[s3]);
        a[mp[s3]].push_back(mp[s2]);
        a[mp[s3]].push_back(mp[s1]);
    }
    if(mp.find("Isenbaev")==mp.end()){
        for(auto b:mp)
            cout<<b.first<<" undefined"<<endl;
        return 0;
    }
    int root=mp["Isenbaev"];
    q.push(root);
    vis[root]=1;
    rnk[root]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<a[u].size();i++){
            if(!vis[a[u][i]]){
                vis[a[u][i]]=1;
                rnk[a[u][i]]=rnk[u]+1;
                q.push(a[u][i]);
            }
        }
    }
    for(auto b:mp){
        if(rnk[b.second]!=-1)
            cout<<b.first<<' '<<rnk[b.second]<<endl;
        else
            cout<<b.first<<' '<<"undefined"<<endl;
    }
    return 0;
}

Comments