백준 2848번 : 알고스팟어 - 위상정렬 C++ 코드

https://www.acmicpc.net/problem/2848

2848번: 알고스팟어

#include <bits/stdc++.h>
using namespace std;


int n;
vector<string> v;

bool adj[26][26];
int degree[26];
int ch[26];

bool flag = false;
bool flag2 = false;

void comp(string s1, string s2) {
    int a = s1.length();
    int b = s2.length();

    int c = min(a, b);

    bool same = true;
    for (int i = 0; i < c; i++) {
        if (s1[i] != s2[i]) {
            int aa = int(s1[i] - 'a');
            int bb = int(s2[i] - 'a');

            if (adj[aa][bb] == 0) {
				adj[aa][bb] = 1;
				degree[bb]++;
            }

            same = false;
			break;
        }
    }


    //abc
    //ab 예외 처리 

    if (same) {
        if (a > b) flag2 = true;
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        v.push_back(s);

        for (int j = 0; j < s.length(); j++) {
            ch[s[j] - 'a'] = 1;
        }
    }

    for (int i = 0; i < 26; i++) {
        if (ch[i]) cnt++;
    }


    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            comp(v[i], v[j]);
        }
    }

    if (flag2) {
        cout << "!\n";
        return 0;
    }


    queue<int> Q;

	for (int i = 0; i < 26; i++) {
		if (ch[i] == 1 && degree[i] == 0) {
			Q.push(i);
		}
	}


    
    vector<int> ans;
    while (!Q.empty()) {
        if (Q.size() >= 2) {
            flag = true;
            break;
        }

        int x = Q.front();
        Q.pop();
        ans.push_back(x);

        for (int i = 0; i < 26; i++) {
			if (ch[i] == 1 && adj[x][i] == 1) {
				if (--degree[i] == 0) {
					Q.push(i);
				}
			}
		}
    }


    if (flag) {
        cout << "?\n";
    }
    else if (ans.size() != cnt) {
        cout << "!\n";
    }
    else {
        for (auto x: ans) {
            cout << (char)(x + 'a');
        }
        cout << '\n';

    }


    return 0;
}

백준 2848번 알고스팟어 C++