我写了一个,不能肯定是对的。
private class SortItem {
private String name;
private ArrayList prevs = new ArrayList();
private ArrayList nexts = new ArrayList();
private SortItem(String name) {
this.name = name;
}
private boolean setNext(SortItem nextItem) {
if(this.hasNext(nextItem))
return true;
if(this.hasPrev(nextItem))
return false;
for (Iterator iter = nextItem.prevs.iterator(); iter.hasNext();) {
SortItem prev = (SortItem) iter.next();
if(this.hasPrev(prev)) {
iter.remove();
prev.nexts.remove(nextItem);
}
} for (Iterator iter = this.nexts.iterator(); iter.hasNext();) {
SortItem next = (SortItem) iter.next();
if(nextItem.hasNext(next)) {
iter.remove();
next.prevs.remove(this);
}
}
nexts.add(nextItem);
nextItem.prevs.add(this);
return true;
}
private boolean hasNext(SortItem item) {
for (int i = 0; i < nexts.size(); i++) {
SortItem nextItem = (SortItem)nexts.get(i);
if(nextItem.equals(item) || nextItem.hasNext(item))
return true;
}
return false;
} private boolean hasPrev(SortItem item) {
for (int i = 0; i < prevs.size(); i++) {
SortItem prevItem = (SortItem)prevs.get(i);
if(prevItem.equals(item) || prevItem.hasPrev(item))
return true;
}
return false;
}
private SortItem getSortItem(String name) {
for (int i = 0; i < nexts.size(); i++) {
SortItem nextItem = (SortItem)nexts.get(i);
if(nextItem.name.equals(name))
return nextItem;
SortItem ret = nextItem.getSortItem(name);
if(ret != null)
return ret;
}
return null;
}
public int hashCode() {
return name.hashCode();
}
public boolean equals(Object obj) {
if(obj instanceof SortItem) {
return name.equals(((SortItem)obj).name);
}
return false;
}
public String toString() {
StringBuffer sb = new StringBuffer();
sb.append(name).append(":{");
for (int i = 0; i < nexts.size(); i++) {
sb.append(nexts.get(i)).append(",");
}
sb.append("}");
return sb.toString();
}
}
private void sortInput() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = null;
SortItem link = new SortItem("");
while((line = br.readLine()) != null && line.length() > 0) {
String first = line.substring(0,line.indexOf(' '));
String second = line.substring(line.indexOf(' ') + 1);
SortItem firstItem = link.getSortItem(first);
SortItem secondItem = link.getSortItem(second);
if(firstItem == null) {
firstItem = new SortItem(first);
link.setNext(firstItem);
}
if(secondItem == null)
secondItem = new SortItem(second);
firstItem.setNext(secondItem);
}
System.out.println(link);
}
public static void main(String[] args) throws Exception {
new Test().sortInput();
}
private class SortItem {
private String name;
private ArrayList prevs = new ArrayList();
private ArrayList nexts = new ArrayList();
private SortItem(String name) {
this.name = name;
}
private boolean setNext(SortItem nextItem) {
if(this.hasNext(nextItem))
return true;
if(this.hasPrev(nextItem))
return false;
for (Iterator iter = nextItem.prevs.iterator(); iter.hasNext();) {
SortItem prev = (SortItem) iter.next();
if(this.hasPrev(prev)) {
iter.remove();
prev.nexts.remove(nextItem);
}
} for (Iterator iter = this.nexts.iterator(); iter.hasNext();) {
SortItem next = (SortItem) iter.next();
if(nextItem.hasNext(next)) {
iter.remove();
next.prevs.remove(this);
}
}
nexts.add(nextItem);
nextItem.prevs.add(this);
return true;
}
private boolean hasNext(SortItem item) {
for (int i = 0; i < nexts.size(); i++) {
SortItem nextItem = (SortItem)nexts.get(i);
if(nextItem.equals(item) || nextItem.hasNext(item))
return true;
}
return false;
} private boolean hasPrev(SortItem item) {
for (int i = 0; i < prevs.size(); i++) {
SortItem prevItem = (SortItem)prevs.get(i);
if(prevItem.equals(item) || prevItem.hasPrev(item))
return true;
}
return false;
}
private SortItem getSortItem(String name) {
for (int i = 0; i < nexts.size(); i++) {
SortItem nextItem = (SortItem)nexts.get(i);
if(nextItem.name.equals(name))
return nextItem;
SortItem ret = nextItem.getSortItem(name);
if(ret != null)
return ret;
}
return null;
}
public int hashCode() {
return name.hashCode();
}
public boolean equals(Object obj) {
if(obj instanceof SortItem) {
return name.equals(((SortItem)obj).name);
}
return false;
}
public String toString() {
StringBuffer sb = new StringBuffer();
sb.append(name).append(":{");
for (int i = 0; i < nexts.size(); i++) {
sb.append(nexts.get(i)).append(",");
}
sb.append("}");
return sb.toString();
}
}
private void sortInput() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = null;
SortItem link = new SortItem("");
while((line = br.readLine()) != null && line.length() > 0) {
String first = line.substring(0,line.indexOf(' '));
String second = line.substring(line.indexOf(' ') + 1);
SortItem firstItem = link.getSortItem(first);
SortItem secondItem = link.getSortItem(second);
if(firstItem == null) {
firstItem = new SortItem(first);
link.setNext(firstItem);
}
if(secondItem == null)
secondItem = new SortItem(second);
firstItem.setNext(secondItem);
}
System.out.println(link);
}
public static void main(String[] args) throws Exception {
new Test().sortInput();
}
A B //表示A在B的前面
A C //表示A在C的前面
D A //表示D在A的前面
C B //表示C在B的前面由此得到唯一个序列 D A C B其实我的算法比较笨,应该可以再使用一些优化的算法的如果上述的结果一定能够得到唯一序列而不需要考虑条件不全或者有冲突的情况,我可以考虑到另外一种比较好的方法,即先查找第二列的那个字母N,则它必定为第一个。
去掉以字母N为第一列的记录,其中这些记录的第二列为(M1,M2,M3)字母,则分别查找是否存在
以M1,M2,M3为第二列的记录,如M1不存在于第二列中,则表示M1为第二个字母如此类推可以得到整个序列,但是这个算法必须条件完全和正确,
而我上面的代码就有考虑到条件不完全的情况(当然可以还是有问题)