首先，\(max(p,q)\)是下界，因为连一条边最多只能减少一个零入度点和一个零出度点，而最终的图不可能有哪怕一个零出度点或者零入度点（最后的图刚好就是一个点）
根据这个下界，我们也很容易可以构造出来一种方法，让零出度点和另一个SCC的零入度点相连即可，就像下面一样（红色边是添加的边）
acwing367证明
发布时间 2023-10-27 22:34:58作者: 最爱丁珰
首先，\(max(p,q)\)是下界，因为连一条边最多只能减少一个零入度点和一个零出度点，而最终的图不可能有哪怕一个零出度点或者零入度点（最后的图刚好就是一个点）
根据这个下界，我们也很容易可以构造出来一种方法，让零出度点和另一个SCC的零入度点相连即可，就像下面一样（红色边是添加的边）