首页 > 代码库 > 找割顶的模板

找割顶的模板

用邻接矩阵写的。自己慢慢理解吧

#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;}