把那些SFW之类的映射成从0到n-1的数字。这样就可以套用Y总的加边模板。
不过映射要双向映射,因为输出的时候还得找到数字对应的名字
那就变成一个求拓扑排序的模板题了,直接写个拓扑排序完事。
不过这道题的图比较特殊,实际上是一条长长的链,除了头尾,中间节点的入度与出度均为1,所以直接找到头结点,直接沿着链子方向遍历一次也可以。
#include <iostream>
#include <unordered_map>
#include <cstring>
#include <queue>
using namespace std;
const int N = 10010, M = 2 * N;
int n;
int h[N], e[M], ne[M], idx;
unordered_map<string, int> hash1;
unordered_map<int, string> hash2;
int ind[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void topoSort(int s)
{
queue<int> q;
q.push(s);
while (!q.empty())
{
auto t = q.front(); q.pop();
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (--ind[j] == 0)
{
q.push(j);
cout << ' ' << hash2[t] << '-' << hash2[j];
}
}
}
puts("");
}
int main()
{
int T;
cin >> T;
for (int u = 1; u <= T; ++u)
{
cin >> n;
idx = 0;
memset(h, -1, sizeof h);
memset(ind, 0, sizeof ind);
hash1.clear(), hash2.clear();
int cnt = 0;
for (int i = 0; i < n; ++i)
{
string from, to;
cin >> from >> to;
if (hash1.count(from) == 0)
hash1[from] = cnt++, hash2[hash1[from]] = from;
if (hash1.count(to) == 0)
hash1[to] = cnt++, hash2[hash1[to]] = to;
add(hash1[from], hash1[to]);
++ind[hash1[to]];
}
for (int i = 0; i < cnt; ++i)
if(ind[i] == 0)
{
cout << "Case #" << u << ":";
topoSort(i);
break;
}
}
return 0;
}