史先生 网站建设百度企业邮箱注册申请

【题目链接】

ybt 1522：网络
OpenJudge 百练 1144:Network

【题目考点】

1. 图论：割点

【解题思路】

每个交换机是一个顶点，如果两地点之间有电话线连接，那么两顶点之间有一条无向边，该图是无向图。
初始时任何地点之间都是可以通讯的，也就是说这是一个无向连通图。
如果一个交换机停止工作，导致其它一些地点不能通讯，这样的地点交灾区。那么也就是图中去掉该顶点后，有些顶点之间不再连通（没有路径），那么也就是整个图不再是连通图。这样的点就是割点。
灾区就是割点，统计灾区的数量就是统计割点的数量。
使用tarjan算法求出所有割点，将割点保存在一个set中，或用数组标记哪些顶点是割点，而后统计割点数量。

【题解代码】

解法1：Tarjan算法求割点，使用set保存割点

#include <bits/stdc++.h>
using namespace std;
#define N 105
int n, m;
vector<int> edge[N];//edge[i]：顶点i的邻接点 
int dfn[N], low[N], ts, root;
set<int> cutVer;
void tarjan(int u)
{int child = 0;dfn[u] = low[u] = ++ts;for(int v : edge[u]){if(dfn[v] == 0){tarjan(v);low[u] = min(low[u], low[v]);if(u == root && ++child > 1 || u != root && dfn[u] <= low[v])cutVer.insert(u);}elselow[u] = min(low[u], dfn[v]);} 
}
int main()
{int f, t;while(cin >> n && n != 0){ts = 0;//变量初始化 for(int i = 1; i <= n; ++i)edge[i].clear();memset(dfn, 0, sizeof(dfn));cutVer.clear();while(cin >> f && f != 0)while(cin.get() != '\n'){cin >> t;edge[f].push_back(t);edge[t].push_back(f);}for(int v = 1; v <= n; ++v) if(dfn[v] == 0)tarjan(root = v);cout << cutVer.size() << endl;}return 0;
}

解法2：Tarjan算法求割点，使用标记数组保存割点

#include <bits/stdc++.h>
using namespace std;
#define N 105
int n, dfn[N], low[N], ts, root, ct;
vector<int> edge[N];
bool cutVer[N];//cutVer[i]：i是否是割点
void tarjan(int u)
{int child = 0;dfn[u] = low[u] = ++ts;for(int v : edge[u]){if(dfn[v] == 0){tarjan(v);low[u] = min(low[u], low[v]);if(u == root && ++child > 1 || u != root && dfn[u] <= low[v])cutVer[u] = true;//u是割点 }elselow[u] = min(low[u], dfn[v]); }
} 
int main()
{int f, t;while(cin >> n && n != 0){ts = ct = 0;//变量初始化 for(int i = 1; i <= n; ++i)edge[i].clear();memset(cutVer, 0, sizeof(cutVer));memset(dfn, 0, sizeof(dfn));while(cin >> f && f != 0)while(cin.get() != '\n'){cin >> t;edge[f].push_back(t);edge[t].push_back(f);}for(int v = 1; v <= n; ++v) if(dfn[v] == 0)tarjan(root = v);for(int v = 1; v <= n; ++v) if(cutVer[v])//统计割点数量 ct++;cout << ct << endl;}return 0;
}