static string ans[] = { "Yes", "No" };
static int group[200];
static map<string, int> table;
static void set_graph(string& s1, string& s2, list<int> * graph)
{
int p1, p2;
map<string, int>::iterator itr;
if ((itr = table.find(s1)) == table.end())
{
p1 = table.size();
table.insert(pair<string, int>(s1, p1));
}
else
p1 = itr->second;
if ((itr = table.find(s2)) == table.end())
{
p2 = table.size();
table.insert(pair<string, int>(s2, p2));
}
else
p2 = itr->second;
graph[p1].push_back(p2);
graph[p2].push_back(p1);
}
static int all_visited()
{
int cnt = table.size(), ret = -1;
for (int i = 0; i < cnt; i++)
{
if (!group[i])
{
ret = i;
break;
}
}
return ret;
}
static int bfs(list<int> * graph, int s)
{
int ret = 0;
queue<pair<int, int>> next_visit; //to, from
next_visit.push(pair<int, int>(s, s));
while (!next_visit.empty())
{
int cur = next_visit.front().first;
int from = next_visit.front().second;
next_visit.pop();
if (!group[from])
{
group[from] = 1;
}
else if (!group[cur])
{
group[cur] = (group[from] == 2 ? 1 : 2);
}
else
{
if (group[cur] == group[from])
{
ret = 1;
break;
}
}
list<int> &adj = graph[cur];
while (!adj.empty())
{
if (!group[adj.front()])
next_visit.push(pair<int, int>(adj.front(), cur));
adj.pop_front();
}
}
return ret;
}
static int divide_team(list<int> * graph)
{
int ret = 0, cnt = table.size(), s;
while ((s = all_visited()) >= 0)
{
if ((ret = bfs(graph, s)) == 1)
break;
}
return ret;
}
static string& solution(void)
{
int ret = 0, K;
string s1, s2;
list<int> graph[200];
cin >> K;
for (int i = 1; i <= K; i++)
{
cin >> s1 >> s2;
set_graph(s1, s2, graph);
}
memset(group, 0, sizeof(int) * 200);
ret = divide_team(graph);
table.clear();
return ans[ret];
}시너지를 갖는 사람들을 먼저 그래프로 묶는다.
그러다 보면 모든 사람들이 같은 그래프에 묶일 수도 있지만, 연결되지 않은 두개의 그래프로 표현되어질 수 도 있다.
즉, 별개의 두 집단이 형성되는 것이다.
그래서 bfs를 한번 돌려서 모든 정점에 방문 하지 못할 수 있어서,
bfs를 마치고나서 아직도 방문하지 못한 정점을 찾고 그 정점을 시작으로 bfs를 반복하는 것이다.
다음은 셋업된 그래프를 이용하여 시너지를 안내게 팀원들을 가르는 방식이다.
맨 처음으로 선택된 사람(시작 정점)은 1번 그룹, 2번 그룹 중 아무곳에나 들어가도 된다.
여기서 1번에 먼저 넣는다고 가정하면, 1번에 들어간 사람과 시너지를 내는 (인접한 정점) 사람은 무조건 2번 그룹에만 들어가야 된다. 그리고 2번그룹에 들어간 사람과 시너지를 내는 사람 들 중 아직 방문하지 않은 사람들은 무조건 1번에만 들어가야 된다. 이런식으로 bfs를 살짝 수정하여 코드를 구현하였다.
마지막은 실패하는 경우에 대한 것이다.
앞서 설명한 방식대로 동작하던 와중에 아직 방문하지 않아 큐에 push된 상태에서 다른 정점에 의해 방문되어질 수 있다. 이에 대해 처리하는 것이 bfs() 에서 세번째 else이다.
예를 하나 들면,
A - B - C
B - A - C
C - A - B
에서
1번 그룹 2번 그룹
A(1) B(2) q의 상태 : C(from A) - C(from B) - (a)
C(3) q의 상태 : C(from B)
괄호는 반복의 실행 순서이다.
먼저 A가 1번 그룹에 들어가고 인접한 B, C를 큐에 넣는다.
이제 B가 pop되어 A와 다른 그룹인 2번 그룹에 들어가게 된다. 이 순간에 C는 아직 방문하지 않았기에 q에 들어간다.
그래서 q의 상태가 (a)와 같은 것이다.
이제 C를 pop하여 A와 다른 2번 그룹에 넣는다. C 입장에서 인접한 정점들은 모두 방문되었기에 큐에 넣을 수 없다.
마지막으로 C를 다시 pop한다.
이 때 C는 B에서 부터 온 것이다. 그런데 B 와 C는 같은 그룹에 있다. 그래서 시너지를 안내게 팀을 나눌 수 없는 것이다.
그래서 이런 경우에는 "No" 를 출력하게 되는 것이다.