DICTIONARY - 고대어 사전 (위상정렬)

https://algospot.com/judge/problem/read/DICTIONARY

위상정렬 기본예제. dfs로 위상정렬 순서 정해주는 것 기록용

 

<설명>

알파벳의 순서를 그래프로 표현하여 사이클이 있다면 INVALID 출력, 없다면 위상정렬된 순서로 출력

 

<풀이>

생략. dfs부분 유념

 

<코드>

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <utility>
#include <tuple>
#include <functional>
#include <cmath>
#define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MAX = 1e3 + 4;

int n; string a[MAX];
vector<int> adj[26], tps;
bool vst[26], fin[26],cycle;

void init() {
	for (int i = 0; i < 26; i++) {
		adj[i].clear();
		vst[i] = fin[i] = 0;
	}
	tps.clear();
	cycle = false;
}
//**********위상정렬************//
void dfs(int u) {
	vst[u] = true;

	for (int v : adj[u]) {
		if (vst[v]) {
			if (!fin[v]) cycle = true;
			continue;
		}
		dfs(v);
	}

	fin[u] = true;
	tps.push_back(u);
}

int main() {
	FAST;
	int tt; cin >> tt;
	while (tt--) {
		init();	cin >> n;
		for (int i = 0; i < n; i++) cin >> a[i];

		for (int i = 0; i < n-1; i++) {
			for (int j = i + 1; j < n; j++) {
				for (int k = 0; k < min(a[i].size(), a[j].size()); k++) {
					if (a[i][k] == a[j][k]) continue;
					adj[a[i][k]-'a'].push_back(a[j][k]-'a');
					break;
				}
			}
		}

		for (int i = 0; i < 26; i++)
			if (!vst[i] && !adj[i].empty()) dfs(i);

		if (cycle) {
			cout << "INVALID HYPOTHESIS\n";
			continue;
		}
		reverse(tps.begin(), tps.end());
		for (int i : tps) cout << char(i + 'a');
		for(int i=0;i<26;i++) if(!vst[i]) cout << char(i + 'a');
		cout << '\n';
	}
}