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

#define SIZE 20
class Deg{
private:
 map<string,int> list;
 int size;
 int graph[SIZE][SIZE];
 void initGraph();
 void createGraph();
public:
 bool read();
 void print();
};

void Deg::initGraph(){
 int i,j;
 for(i=0;i<SIZE;i++)
  for(j=0;j<SIZE;j++)
   i==j?graph[i][j]=0:graph[i][j]=-1;
}

bool Deg::read(){

 initGraph();

 string name,fri;
 int id=1,degs;
 cin>>size;
 for(int i=0;i<size;i++){
  cin>>name;
  if(list[name]==0)
   list[name]=id++;
  cin>>degs;
  for(int j=0;j<degs;j++){
   cin>>fri;
   if(list[fri]==0)
    list[fri]=id++;
   graph[list[name]-1][list[fri]-1]=1;
  }
 }
 return true;
}

void Deg::print(){

 createGraph();

 int times,i,dis;
 string start,goal;
 cin>>times;
 for(i=0;i<times;i++){
  cin>>start>>goal;
  dis=graph[list[start]-1][list[goal]-1];
  if(dis>0)
   cout<<start<<" is separated from "<<goal<<" by "<<dis-1<<" degrees.";
  else
   cout<<start<<" has no connection to "<<goal<<".";
  cout<<endl;
 }
}

void Deg::createGraph(){
 int i,j,k,dest;
 for(k=0;k<size;k++)
  for(i=0;i<size;i++)
   for(j=0;j<size;j++)
    if(graph[i][k]!=-1 && graph[k][j]!=-1){
     dest=graph[i][k]+graph[k][j];
     if(graph[i][j]==-1)
      graph[i][j]=dest;
     else if(graph[i][j]>dest)
      graph[i][j]=dest;
    }
}

int main(){
 Deg deg;
 deg.read();
 deg.print();
 return 0;
}


评论

该日志第一篇评论

发表评论

评论也有版权!