#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;
}
#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
Post a Comment