已知有一个有向图 GGG,它包含了 VVV 个点和 SSS 条边,记 f(i,j)f(i,j)f(i,j) 表示第 iii 个点和第 jjj 个点之间有一条有向边,由 iii 指向 jjj。
若存在两个点:aaa,bbb 满足 f(a,b)f(a,b)f(a,b) 和 f(b,a)f(b,a)f(b,a) 则删除 a,ba,ba,b,由 aaa 指向 bbb 的边和由 bbb 指向 aaa 的边,但是不删除由除 a,ba,ba,b 之外的点指向 a,ba,ba,b 的边。
求证:最后剩下的途中必然存在一个环或一个链。
环:a→b→...→aa \rightarrow b \rightarrow ... \rightarrow aa→b→...→a
链:a→b→c→...→?→a \rightarrow b \rightarrow c \rightarrow... \rightarrow ? \rightarrowa→b→c→...→?→