| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 4902 | Accepted: 1982 |
Description
This problem involves neither Zorn's Lemma nor fix-point semantics, but does involve order.
Given a list of variable constraints of the form x < y, you are to write a program that prints all orderings of the variables that are consistent with the constraints.
For example, given the constraints x < y and x < z there are two orderings of the variables x, y, and z that are consistent with these constraints: x y z and x z y.
Input
All variables are single character, lower-case letters. There will be at least two variables, and no more than 20 variables in a specification. There will be at least one constraint, and no more than 50 constraints in a specification. There will be at least one, and no more than 300 orderings consistent with the contraints in a specification.
Input is terminated by end-of-file.
Output
Output for different constraint specifications is separated by a blank line.
Sample Input
a b f g
a b b f
v w x y z
v y x v z v w v
Sample Output
abfg
abgf
agbf
gabf wxzvy
wzxvy
xwzvy
xzwvy
zwxvy
zxwvy
Source
/*
Problem:
OJ:
User: S.B.S.
Time:
Memory:
Length:
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<sstream>
#include<queue>
#include<cstdlib>
#include<iomanip>
#include<cassert>
#include<climits>
#include<functional>
#include<bitset>
#include<vector>
#include<list>
#include<map>
#define F(i,j,k) for(int i=j;i<=k;i++)
#define M(a,b) memset(a,b,sizeof(a))
#define FF(i,j,k) for(int i=j;i>=k;i--)
#define maxn 10001
#define inf 0x3f3f3f3f
#define maxm 1001
#define mod 998244353
//#define LOCAL
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m;
int a[maxn],d[maxn];
int pos[maxn],cnt[maxn][];
bool vis[maxn];
inline void dfs(int u)
{
if(u>n){
F(i,,n) cout<<(char)a[i];
cout<<endl;
return;
}
F(i,,n){
if(!vis[i]){
a[u]=d[i];
pos[a[u]]=u;
vis[i]=true;
bool flag=true;
for(int j=;j<=m&&flag;j++)
{
int aa=cnt[j][],bb=cnt[j][];
if(pos[aa]==||pos[bb]==||pos[aa]<pos[bb]);
else flag=false;
}
if(flag) dfs(u+);
pos[a[u]]=;
vis[i]=false;
}
}
}
int main()
{
// std::ios::sync_with_stdio(false);//cout<<setiosflags(ios::fixed)<<setprecision(1)<<y;
#ifdef LOCAL
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
string s;
istringstream ss;
char aa,bb,cc;
while(getline(cin,s))
{
M(vis,);M(pos,);
n=m=;ss.clear();
ss.str(s);
while(ss>>cc) d[++n]=cc;
sort(d+,d+n+);
getline(cin,s);
ss.clear();
ss.str(s);
while(ss>>aa>>bb){
cnt[++m][]=aa;
cnt[m][]=bb;
}
dfs();
cout<<endl;
}
return ;
}
poj 1270