百度提交网站已删内容,怎么制作软件程序,哪种源码做视频网站好用,聊城企业门户网站建设【题目链接】
ybt 1522#xff1a;网络 OpenJudge 百练 1144:Network
【题目考点】
1. 图论#xff1a;割点
【解题思路】
每个交换机是一个顶点#xff0c;如果两地点之间有电话线连接#xff0c;那么两顶点之间有一条无向边#xff0c;该图是无向图。 初始时任何地…【题目链接】
ybt 1522网络 OpenJudge 百练 1144:Network
【题目考点】
1. 图论割点
【解题思路】
每个交换机是一个顶点如果两地点之间有电话线连接那么两顶点之间有一条无向边该图是无向图。 初始时任何地点之间都是可以通讯的也就是说这是一个无向连通图。 如果一个交换机停止工作导致其它一些地点不能通讯这样的地点交灾区。那么也就是图中去掉该顶点后有些顶点之间不再连通没有路径那么也就是整个图不再是连通图。这样的点就是割点。 灾区就是割点统计灾区的数量就是统计割点的数量。 使用tarjan算法求出所有割点将割点保存在一个set中或用数组标记哪些顶点是割点而后统计割点数量。
【题解代码】
解法1Tarjan算法求割点使用set保存割点
#include bits/stdc.h
using namespace std;
#define N 105
int n, m;
vectorint edge[N];//edge[i]顶点i的邻接点
int dfn[N], low[N], ts, root;
setint 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;
}解法2Tarjan算法求割点使用标记数组保存割点
#include bits/stdc.h
using namespace std;
#define N 105
int n, dfn[N], low[N], ts, root, ct;
vectorint 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;
}
