#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
vector<vector<int>> adj; //인접행렬
vector<string> s;//string을 넣는 vector
vector<int> seen;//방문 여부
vector<int> list;
void dfs(int here) {//dfs탐색
seen[here] = 1;
for (int i = 0; i < adj.size(); i++) {
if (adj[here][i] && !seen[i])
dfs(i);
}
list.push_back(here);//방문한것을 list에 넣는다.
}
vector<int> dfsAll(void) {//컴포넌트를 모두 순회하기 위해서.
int n = adj.size();
seen = vector<int>(n, 0);//초기화를 진행한다(오버라이딩)
list.clear();
for (int i = 0; i < n; i++)
if (!seen[i])
dfs(i);
reverse(list.begin(), list.end());
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (adj[list[j]][list[i]]) return vector<int>();
}
}
return list;
}
/*인접 행렬을 만드는 부분*/
void makegragh(const vector<string>& words) {
adj = vector<vector<int>>(26, vector<int>(26, 0));//그래프 초기화를 실행
for (int i = 1; i < words.size(); i++) {//j,i
int j = i - 1;
int len = min(words[i].size(), words[i].size());
for (int k = 0; k < len; k++) {
if (words[i][k] != words[j][k]) {
int a = words[j][k] - 'a';
int b = words[i][k] - 'a';
adj[a][b] = 1;
break;
}
}
}
}
int main(void) {
int T;
int n;
vector<int> l;
cin >> T;
for (int i = 0; i < T; i++) {
//초기화 공정
adj.clear();
s.clear();
l.clear();
cin >> n;
s = vector<string>(n);
for (int j = 0; j < n; j++) {
cin >> s[j];
}
makegragh(s);
l = dfsAll();
if (l == vector<int>())
cout << "INVALID HYPOTHESIS" << endl;
else {
for (int k = 0; k < 26; k++)
cout << (char)(l[k]+'a');
cout << endl;
}
}
return 0;
}
(C++ 소스 코드)
DICTIONARY문제인데요....
혼자공부하면서 원리이해하고, 책에있는내용을 다시 치면서
맞나 하면서 올려봤는데 계속 RTE (SIGSEGV: segmentation fault, probably incorrect memory access or stack overflow)가 뜨네요....
제 컴퓨터에서는 잘돌아가지만... 올리면 계속 같은 메세지가
떠서... 왜그러는지 혹시 아시면 조언 부탁드리겠습니다.
dexaboud3
DICTIONARY문제인데요....
혼자공부하면서 원리이해하고, 책에있는내용을 다시 치면서
맞나 하면서 올려봤는데 계속 RTE (SIGSEGV: segmentation fault, probably incorrect memory access or stack overflow)가 뜨네요....
제 컴퓨터에서는 잘돌아가지만... 올리면 계속 같은 메세지가
떠서... 왜그러는지 혹시 아시면 조언 부탁드리겠습니다.
9년 전