Erdos Numbers

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <limits>
#include <time.h>
using namespace std;
#define mycom
#ifdef mycom
#include <fstream>
ifstream fin("input");
#else
#define fin cin
#endif

struct Node
{
 string vertex;
 Node* adj;
 bool operator==(const Node& n) const
 {
  return (vertex == n.vertex);
 }
 bool operator<(const Node& n) const
 {
  return vertex < n.vertex;
 }
};


vector<Node> graph;


void CreateVertex(const string& v)
{
 Node n;
 n.vertex = v;
 n.adj = 0;
 bool bfind = false;
 if( find(graph.begin(), graph.end(), n) == graph.end() ) // 없
  graph.push_back(n);
}


void link(const string& from, const string& to)
{
 Node s;
 s.vertex = from;
 vector<Node>::iterator fromiter = find(graph.begin(), graph.end(), s);
 Node* p = new Node;
 p->vertex = to;
 p->adj = fromiter->adj;
 fromiter->adj = p;
}


int sina;
int non;
int saram;

 


int mymin = 9999999;
map<string, bool> visit;
void dfs(const string& curnode, int mycount)
{
 //해가 맞는가?
 //아니면
 //모든 경우에 대해 백트
 visit[curnode] = true;
 ///cout << curnode << endl;
 if(curnode == "Erdos, P.")
 {
  if (mycount < mymin)
   mymin = mycount;
 } else
 {
  Node s;
  s.vertex = curnode;
  Node* p = &(*find(graph.begin(), graph.end(), s));
  while(p)
  {   
   if(mymin > mycount )
   {
    if( p->adj && !visit[p->adj->vertex] )
     dfs(p->adj->vertex, mycount + 1);
   }
   p = p->adj;
  }
 }
 visit[curnode] = false;
}


int main()
{

 
 fin >> sina;
 for (int i = 1; i <= sina; i++)
 {
  //memset(graph, 0, sizeof(graph));


  fin >> non >> saram;
  //
  char t;
  while (fin.get(t) && t != '\n')
   ;
  
  for (int j = 1; j <= non; j++)
  {


   char temp[1024];
   fin.getline(temp, 1024);
   int startpos = 0;
   vector<string> v;
   for (int i = 0; i < strlen(temp); i++)
   { // 문자열 파싱.
    if (strncmp(&temp[i], ".,", 2) == 0 || strncmp(&temp[i], ".:", 2) == 0)
    {
     string strtemp;
     strtemp.assign(&temp[startpos], &temp[i + 1]);
     v.push_back(strtemp);


     startpos = i + 3;
    }
   }

   
   //이어주기
   for (int z = 0; z < v.size(); z++)
   {
    for (int z2 = 0; z2 < v.size(); z2++)
    {
     if(z != z2)
     {
      CreateVertex(v[z]);
      CreateVertex(v[z2]);
      link(v[z], v[z2]);
      //link(v[z2], v[z]);
     }
    }
   }
   
  }
  
  //for(map<string, int>::iterator i = dic.begin(); i != dic.end(); i++)
  // cout << i->first << i->second << endl;
  //while (fin.get(t) && t != '\n');
  cout << "Scenario " << i << endl;
  
  char temp[1024];
  for (int j = 1; j <= saram; j++)
  {
   fin.getline(temp, 1024);
   
   mymin = numeric_limits<int>::max();
   clock_t start = clock(); 
   dfs(temp, 0);
   //cout << clock() - start << endl;
   if (mymin == numeric_limits<int>::max())
    cout << temp << " " << "infinity" << endl;
   else
    cout << temp << " " << mymin << endl;
  }
 }


 return 0;
}