1 #include<bits/stdc++.h>2usingnamespace std;3constint maxn=5005;4int N,M;5int stac[maxn],top=0;//Tarjan算法中的栈 6bool instac[maxn];//检查是否在栈中 7int dfn[maxn];//深度优先搜索访问次序 8int low[maxn];//能追溯到的最早的次序 9int tot=0;//有向图强连通分量个数10int index=0;//索引号11 vector<int>to[maxn]; 12 vector<int> kin[maxn];//获得强连通分量结果13int inkin[maxn];//记录每个点在第几号强连通分量里...
最近在学图论相关的内容，阅读这篇博客的前提是你已经基本了解了Tarjan求点双。由割点的定义（删去这个点就可使这个图不连通）我们可以知道，坍塌的挖煤点只有在割点上才会使这个图不连通，而除了割点的其他点上则无可厚非，所以我们只需要考虑这个图的割点的情况。 那么我们就可以求出所有的点双连通分量， 如果这个点双仅有一个割点，那么这个割点坍塌后这个点双就被“孤立”了，所以需要在这个点双里设置一个救援出口。 那么这...