首页 > 代码库 > 找割顶的模板
找割顶的模板
用邻接矩阵写的。自己慢慢理解吧
#include <iostream>#include <cstring>using namespace std;#define CC(c) memset(c, 0, sizeof(c))const int maxn=5000;int iscut[maxn], g[maxn][maxn], low[maxn], pre[maxn], _pre, n, m;int dfs(int u, int fa) { low[u]=pre[u]=++_pre; //初始时 int child=0; //如果child=1并且它是根,就不是割顶 for(int v=1; v<=n; ++v) if(g[u][v]) { if(!pre[v]) { child++; int lowv=dfs(v, u); //找子女的最小low,看是否能回溯到自己的fa前面 if(lowv<low[u]) low[u]=lowv; //更新最小 if(lowv>=pre[u]) iscut[u]=1; //如果在fa后面,即没有指向fa前面,就是一个割顶 } else if(pre[v]<pre[u] && v!=fa && low[u]>pre[v]) //因为是无向图,所以要判断是否是之前的访问的第二次访问回去的环 low[u]=pre[v]; } if(fa<0 && child==1) iscut[u]=0; return low[u];}void find_cut() { CC(iscut); CC(low); CC(pre); for(int i=1; i<=n; ++i) if(!pre[i]) dfs(i, -1); for(int i=1; i<=n; ++i) if(iscut[i]) cout << i << " "; cout << endl;}int main() { cin >> n >> m; for(int i=1; i<=n; ++i) { int a, b; cin >> a >> b; g[a][b]=g[b][a]=1; } find_cut(); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。