알고리즘/Codeforces

Edu82(Div.2) C. Perfect Keyboard

세진짱 2020. 2. 16. 16:35

dfs를 이용한 cycle 체크 문제 응용
만약 cycle이 있다면 NO이다
하지만 몇가지 조건이 더 있다
먼저 각 정점마다 최대 2개의 간선을 가지므로 indgree가 2보다 크면 fail
또한 cycle을 확인할 때 set을 통해 이미 본 간선은 지워준다고 생각하고 푼다
출력하는건 indgree가 낮은곳부터 쭉 dfs를 통해 출력하고 남은걸 출력하면 된다
 

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
vector<int> Graph[26];
int ind[26];
int visited[26];
bool edge[26][26];
bool check[26][26];
int n;
set<pair<int, int>> st;
bool isCycle(int now) {
    if (visited[now]) {
        if (visited[now] == -1) return true;
        return false;
    }
    visited[now] = -1;
    for (int i = 0; i < Graph[now].size(); i++) {
        int next = Graph[now][i];
        if (st.count({ now,next }) || st.count({ next,now })) continue;
        st.insert({ now,next });
        if (isCycle(next)) return true;
    }
    visited[now] = 1;
    return false;
}
 
void init() {
    memset(ind, 0, sizeof(ind));
    memset(visited, 0, sizeof(visited));
    memset(edge, 0, sizeof(edge));
    st.clear();
    for (int i = 0; i < 26; i++) Graph[i].clear();
}
 
void print(int x) {
    printf("%c", x + 'a');
    visited[x] = true;
    for (int i = 0; i < Graph[x].size(); i++) {
        if (!visited[Graph[x][i]]) print(Graph[x][i]);
    }
}
 
int main() {
    scanf(" %d,", &n);
    for (int tc = 0; tc < n; tc++) {
        init();
        string s; cin >> s; int sz = s.size();
 
        for (int i = 0; i < sz - 1; i++) {
            int x = s[i] - 'a', y = s[i + 1] - 'a';
            if (edge[x][y] & edge[y][x]) continue;
            edge[x][y] = edge[y][x] = true;
            Graph[x].push_back(y);
            Graph[y].push_back(x);
            ind[x]++; ind[y]++;
        }
 
        bool degree = true;
        for (int i = 0; i < 26; i++) if (ind[i] > 2) degree = false;
        if (!degree || isCycle(s[0] - 'a')) puts("NO");
        else {
            puts("YES");
            memset(visited, 0, sizeof(visited));
            int cnt = 1e9, idx = 0;
            for (int i = 0; i < 26; i++) {
                if (!ind[i]) continue;
                if (cnt > ind[i]) {
                    cnt=ind[i]; idx = i;
                }
            }
            print(idx);
            for (int i = 0; i < 26; i++) if (!visited[i]) printf("%c", i + 'a'); puts("");
        }
    }
}
 
  
저작자표시