Boj 1108) 검색엔진

문제

백준 1108

위상정렬을 통해서 만드는 DAG Tree 의 Leaf Node 부터 차례로 점수를 더해주면 되는 문제이다.

이때 전체 사이트의 갯수는 주어진 링크 리스트인 \(N\) 와 링크 리스트 당 등장할 사이트의 갯수인 \(1 + 24\) 와 같다는 것에 주의하자.

시간 복잡도

O(\(25N\))

코드

const int MAX_SIZE = 51 * 24;
vector<int> edges[MAX_SIZE];
stack<int> st;
int visits[MAX_SIZE], n_visit;
int roots[MAX_SIZE], n_roots;

int SCC(int cur)
{
	int res = visits[cur] = ++n_visit;
	st.push(cur);

	for (auto l : edges[cur])
	{
		if (roots[l]) continue;
		if (visits[l]) res = min(res, visits[l]);
		else res = min(res, SCC(l));
	}

	if (res == visits[cur])
	{
		n_roots++;
		while (1)
		{
			int tmp = st.top();
			roots[tmp] = n_roots;
			st.pop();
			if (tmp == cur) {
				scores[n_roots] = st.size();
				break;
			}
		}
	}
	return res;
}

unordered_map<string, int> sites;
long long scores[MAX_SIZE];

int RegistSite(const string& s)
{
	auto iter = sites.find(s);
	return iter == sites.end() ? sites.emplace(s, sites.size()).first->second : iter->second;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string from, to;
		int m, fromIdx, toIdx;
		cin >> from >> m;
		fromIdx = RegistSite(from);
		while (m--)
		{
			cin >> to;
			toIdx = RegistSite(to);
			edges[fromIdx].push_back(toIdx);
		}
	}
	for (int i = 0; i < sites.size(); i++) if (!visits[i]) SCC(i);

	vector<int> rankOrderIndices;
	for (int i = 0; i < sites.size(); i++) rankOrderIndices.push_back(i);
	sort(rankOrderIndices.begin(), rankOrderIndices.end(), [](int a, int b) { return roots[a] < roots[b]; });

	fill(visits, visits + MAX_SIZE, 0);
	fill(scores, scores + MAX_SIZE, 1);
	for (auto idx : rankOrderIndices)
		for (auto l : edges[idx])
			if(roots[idx] != roots[l])  // 같은 SCC 라면 Score 를 추가하지 않는다.
				scores[idx] += scores[l];

	string k; cin >> k;
	cout << scores[RegistSite(k)];
}