Let the edges being:
1 2
2 0
1 3
3 0
1 4
4 0

is the max-flow 3? if true, then disagree since we can wait until the spy enter one of 2, 3 or 4.

1 2
2 0
1 3
3 0
1 4
4 0
1 5
5 0
5 0
5 0
5 0

对min-cut不是很清楚，下面的计算对吗？
MC(1)=4
MC(2)=2
MC(3)=2
MC(4)=2
MC(5)=5

如果是对的，根据你的算法，结果应该是MC(1)=4吧？
不过，先断掉edge 1 5, 然后等一下。可以更好一些。

Let
struct treeNode{
int id;
treeNode *left;
treeNode *right;
treeNode *par;
};

DFS(treeNode *root){
treeNode *cur=root;
while (cur!=NULL){
printf("%d, ", cur->id);
if (cur->left!=NULL){
cur=cur->left;
}
else if (cur->right!=NULL)
cur=cur->right;
else{
treeNode *par=cur->par;
while (par!=NULL){
if (par->left==cur && par->right!=NULL){
cur=par->right;
break;
}
cur=par;
par=par->par;
}
if (par==NULL) cur=NULL;
}
}
}

其实就是depth first, 应该是O(3n)=O(n)吧。