10044 Erdos Numbers 알고리즘

#include <cstdio>
#include <string>
#include <map>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define N 5000
#define INF -1
int erdosIdx,cntName;
map<string,int> nameMap;
multimap<int, int>graph;
int dist[N];
string erdos("Erdos, P.");
void bfs()
{
//에르도스를 시작 정점으로 해서, 그래프를 너비우선검색을 한다.
//한 번 방문한 노드는 방문 당시, 그 경로가 최단 경로이므로 , 더 이상 다시 방문하지 않도록 한다.
//그래프의 가중치는 1이므로, 깊이가 증가할 수록 크기는 이전 노드의 거리에 +1을 해주면 된다.
bool visit[N]={false,};
visit[erdosIdx] = true;
queue<int> q;
q.push(erdosIdx);
for(int i=0; i < cntName; i++)
dist[i] = -1;
dist[erdosIdx]=0;
while(!q.empty())
{
int v = q.front();
q.pop();
pair<multimap<int,int>::iterator,multimap<int,int>::iterator> itPair;
itPair = graph.equal_range(v);
for(multimap<int,int>::iterator it = itPair.first; it != itPair.second; it++)
{
if(!visit[it->second])
{
visit[it->second] = true;
dist[it->second] = dist[v] + 1;
q.push(it->second);
}
}
}
}
int main()
{
int nCase,n,p;
cin>>nCase;
for(int nScenario=1; nScenario <= nCase; nScenario++,nameMap.clear(),graph.clear())
{
cin>>p>>n;
getchar();
cntName=0;
string line;
line.reserve(100000);
while(p--)
{
getline(cin,line);
vector<int> gVec; gVec.reserve(50000);
string s; s.reserve(2000);
int len = line.length();
//논문 DB로부터 저술자(노드)와 저술자 관계(엣지)를 얻어낸다.
for(int i=0; i < len ; i++)
{
//공백을 무시한다. 
while(line[i] == ' ')
{
i++;
}
//LAST NAME, FIRST NAME 형식으로 되있으므로 첫 콤마를 읽음
//LAST NAME완성 시킨다. 
while(line[i] != ',')
{
s.push_back(line[i++]);
}
//콤마를 포함시킨다.
s.push_back(line[i++]);
//다음 글자 혹은 논문의 제목명의 전까지 읽어서 FIRST NAME 완성시킨다.
while(line[i] != ','&&line[i]!=':')
{
s.push_back(line[i++]);
}
//이름에 고유 번호를 부여한다. 
if(nameMap.find(s)==nameMap.end())
{
nameMap.insert(pair<string,int>(s,cntName++));
}
//그리고 해당 논문에 나온 저자의 고유번호를 저장한다. 나중에 그래프를 만들때 쓰임
gVec.push_back(nameMap.find(s)->second);
s.clear();
// : 이후는 쓸모없으므로 없앤다.
if(line[i] == ':')
break;
}
/- 그래프 생성 부분 - 인접 행렬 생성  *-
int sz = gVec.size();
for(int i=0; i < sz; i++)
{
for(int j=0; j < sz;j++)
{
if(i==j)
continue;
graph.insert(pair<int,int>(gVec[i],gVec[j]));
}
}
}
erdosIdx = nameMap.find(erdos)->second;
bfs();
vector<string> author;
vector<int>erodsNum;
while(n--)
{
getline(cin,line);
author.push_back(line);
if(nameMap.find(line)==nameMap.end())
{
erodsNum.push_back(INF);
}
else
{
int x = nameMap.find(line)->second;
erodsNum.push_back(dist[x]);
}
}
cout<<"Scenario "<<nScenario<<endl;
int sz = erodsNum.size();
for(int i=0; i < sz; i++)
{
cout<<author[i]<<" ";
if(erodsNum[i]==INF)
puts("infinity");
else
cout<<erodsNum[i]<<endl;
}
}
return 0;
}

덧글

댓글 입력 영역