Network UVA - 315 求割点数量

xiaoxiao2021-02-28  92

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> #include <vector> using namespace std; const int MaxM = 1e5; int n, cnt; bool f[101][101], mark[101]; int dfn[101], low[101]; void tarjan(int u, int fa) { dfn[u] = low[u] = ++cnt; int k = 0; for (int i = 1; i <= n; i++) if (f[u][i] && i != fa) { if (!dfn[i]) { tarjan(i, u); k++; low[u] = min(low[u], low[i]); if ((k == 2 && u == 1) || (u != 1 && low[i] >= dfn[u])) mark[u] = true; } else low[u] = min(low[u], dfn[i]); } } int main() { while (scanf("%d", &n), n) { int u, v; cnt = 0; memset(mark, 0, sizeof(mark)); memset(f, 0, sizeof(f)); memset(dfn, 0, sizeof(dfn)); while (scanf("%d", &u), u) while (getchar() != '\n') { scanf("%d", &v); f[u][v] = f[v][u] = true; } tarjan(1, 0); int ans = 0; for (int i = 1; i <= n; i++) if (mark[i]) ans++; printf("%d\n", ans); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-68896.html

最新回复(0)