UVA124 Following Orders

Graph, Topological sort(위상정렬), DFS

출처: UVA UVA124 Following Orders


SOL)
현재 시점에서 방문 할 수있는 곳을 쭉 DFS으로 방문하면 된다.
현재 시점에서 방문 할 수 있는 정점의 indegree를 하나 감소 시킨 후
결정!


[-] Collapse

#include<stdio.h>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

string str;
map<char, int> mp;
int adj[30][30];
int indegree[30];
int idx;
char intTochar[30];
bool visit[30];
void init(){
    mp.clear();
    memset(adj, 0, sizeof(adj));
    memset(indegree, 0, sizeof(indegree));
    memset(visit, false, sizeof(visit));
    idx = 0;
}
void setRelation(string str){
    char from, to;
    int u, v;
    for (int i = 0; i < str.length(); i += 4){
        from = str[i];
        to = str[i + 2];
        u = mp[from];
        v = mp[to];
        if (adj[u][v] == 0){
            adj[u][v] = 1;
            indegree[v]++;
        }
    }
}
void mapping(string str){
    vector<char> temp(str.size());
    for (int i = 0; i < temp.size(); i++)
        temp[i] = str[i];
    //사전순으로 방문을 해야하니 알파벳 순서로 소팅!
    sort(temp.begin(), temp.end());
    for (int i = 0; i < temp.size(); i++){
        if (temp[i] == ' ') continue;
        else{
            if (mp.find(temp[i]) == mp.end()){
                mp[temp[i]] = idx++;
                intTochar[idx - 1] = temp[i];
            }
        }
    }
}
void topo(int here, vector<int>& path){
    visit[here] = true;
    path.push_back(here);
    if (path.size() == idx) {
        for (int i = 0; i < path.size(); i++)
            cout << intTochar[path[i]];
        cout << endl;
    }
    for (int i = 0; i < idx; i++){
        if (adj[here][i] > 0)
            indegree[i]--;
    }
    for (int i = 0; i < idx; i++){
        if (indegree[i] == 0 && !visit[i]){
            topo(i, path);
        }
    }
    //복원
    visit[here] = false;
    path.pop_back();
    for (int i = 0; i < idx; i++){
        if (adj[here][i] > 0)
            indegree[i]++;
    }
}

int main(){
    //freopen("input.txt", "r", stdin);
    bool first = true;
    while (getline(cin, str)){
        init();
        if (!first) cout << endl;
        first = false;
        mapping(str);
        getline(cin, str);
        setRelation(str);
        vector<int> start;
        for (int i = 0; i < idx; i++){
            if (indegree[i] == 0)
                start.push_back(i);
        }
        vector<int> path;
        for (int i = 0; i < start.size(); i++){
            topo(start[i], path);
        }
    }
    return 0;
}