OJ Board

Code: Select all

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 30;
bool exists[MAXN];
int inDegree[MAXN];
bool graph[MAXN][MAXN];
int sequence[MAXN];
bool visited[MAXN];
vector<string> answer;
void read()
{
    memset(exists, 0, sizeof exists);
    memset(inDegree, 0, sizeof inDegree);
    memset(graph, 0, sizeof graph);
    answer.clear();
    string line1, line2;
    getline(cin, line1);
    getline(cin, line2);
    for(int i = 0; i < line1.size(); i += 2)
    {
        exists[line1[i]-'a'] = true;
    }
    for(int i = 0; i < line2.size(); i += 4)
    {
        char from = line2[i];
        char to = line2[i + 2];
        graph[from-'a'][to-'a'] = true;
        ++inDegree[to-'a'];
    }
}
void printSolution(int pos)
{
    string res;
    for(int i = 0; i < pos; ++i)
    {
        res.push_back((char)(sequence[i]+'a'));
    }
    answer.push_back(res);
}
void DFS(int node, int pos)
{
    visited[node] = true;
    sequence[pos] = node;
    for(int i = 0; i < MAXN; ++i)
    {
        if(exists[i] && graph[node][i])
        {
            --inDegree[i];
        }
    }
    bool hasChildren = false;
    for(int i = 0; i < MAXN; ++i)
    {
        if(exists[i] && !visited[i] && inDegree[i] == 0)
        {
            DFS(i, pos + 1);
            hasChildren = true;
        }
    }
    visited[node] = false;
    for(int i = 0; i < MAXN; ++i)
    {
        if(exists[i] && graph[node][i])
        {
            ++inDegree[i];
        }
    }
    if(!hasChildren) printSolution(pos+1);
}
void solve(bool printLine)
{
    for(int i = 0; i < MAXN; ++i)
    {
        if(exists[i] && inDegree[i] == 0) DFS(i, 0);
    }
    sort(answer.begin(), answer.end());
    for(int i = 0; i < answer.size(); ++i)
    {
        cout<<answer[i];
        if(i < answer.size()-1 || printLine) cout<<'\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    while(!cin.eof())
    {
        read();
        solve(!cin.eof());
        if(!cin.eof() || true) cout<<'\n';
    }
    return 0;
}
/*
a b f g
a b b f
v w x y z
v y x v z v w v

*/