POJ 1523 SPF
题意:给定一个无向连通图,求割点。并计算出去除每个割点后能将图分为多少块。
思路:裸的求无向图割点。
代码:
/* ID: wuqi9395@126.com PROG: LANG: C++ */ #include<map> #include<set> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<fstream> #include<cstring> #include<ctype.h> #include<iostream> #include<algorithm> using namespace std; #define INF (1<<30) #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, a, n) for (int i = a; i < n; i++) #define per(i, a, n) for (int i = n - 1; i >= a; i--) #define eps 1e-6 #define debug puts("===============") #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) #define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m) typedef long long ll; typedef unsigned long long ULL; const int maxn = 1100; vector<int> g[maxn]; int dfn[maxn], low[maxn], vis[maxn], sub[maxn]; //sub记录每个割点分为多少块 bool cut[maxn], bridge[maxn][maxn]; void cut_bridge(int u, int f, int dep) { vis[u] = 1; dfn[u] = low[u] = dep; int child = 0; for (int i = 0; i < g[u].size(); i++) if (g[u][i] != f) { int v = g[u][i]; if (vis[v] == 1 && dfn[v] < low[u]) low[u] = dfn[v]; //回边更新low值 if (vis[v] == 0) { cut_bridge(v, u, dep + 1); child++; if (low[v] < low[u]) low[u] = low[v]; //通过儿子回到祖先 if (f == -1 && child > 1) cut[u] = true, sub[u] = child; //根节点为割点 if (f != -1 && low[v] >= dfn[u]) cut[u] = true, sub[u]++; //非根节点为割点 if (low[v] > dfn[u]) bridge[u][v] = bridge[v][u] = true; //割边 } } vis[u] = 2; } int main () { int cas = 1; int u, v, mx = 0; //freopen("2.txt", "r", stdin); while(~scanf("%d", &u), u) { mx = max(mx, u); for (int i = 0; i < maxn; i++) g[i].clear(); scanf("%d", &v); mx = max(mx, v); g[u].push_back(v), g[v].push_back(u); while(~scanf("%d", &u), u) { mx = max(mx, u); scanf("%d", &v); mx = max(mx, v); g[u].push_back(v), g[v].push_back(u); } memset(vis, 0, sizeof(vis)); memset(cut, 0, sizeof(cut)); memset(bridge, 0, sizeof(bridge)); memset(sub, 0, sizeof(sub)); cut_bridge(mx, -1, 0); if (cas > 1) puts(""); printf("Network #%d\n", cas++); bool has = false; for (int i = 1; i <= mx; i++) if (sub[i]) printf(" SPF node %d leaves %d subnets\n", i, sub[i] + 1), has = true; if (!has) puts(" No SPF nodes"); mx = 0; } return 0; }