主要是讲一下tarjan算法的正确性
我们的连边方案是对每一对已经有了的婚姻，从女方向男方连边，然后对于交往过的关系，从男方向女方连边
分析题意不难发现，如果某一对夫妻处于一个环中，那么这对婚姻关系就是不稳定的
其实从环这里已经可以看出来是SCC了，我们来简单说明一下
首先，如果一对夫妻在同一SCC里面，那么这对夫妻一定处于一个环中（SCC中任意两个点一定都在一个环中，因为可以从一个点走到另一个点，然后从另一个点又走到这个点，就形成了一个环），也就是关系是不稳定的
其次，如果一对夫妻不处在同一SCC中，但是仍然同时存在一个环中，那么这个环以及夫妻双方各自所在的两个SCC合并起来就构成了一个更大的SCC，与SCC的极大性矛盾
然后介绍一下二分图的做法，主要是每次不要重新跑一遍完整的匈牙利，因为题目是已经给出了一个完备匹配了，每次只用从被破坏的这对夫妻的某个点出发找一条增广路就好了
标签：稳定,一个点,连边,SCC,婚姻,夫妻,一对 From： https://www.cnblogs.com/dingxingdi/p/18091686