# 求已知网络中关键节点，关键线路

• ### 将已知网络关键节点即割点定义为：删除此节点后，存在原网络中联通的节点，在新的网络中不连通

``````#include <cstdio>
{
static int tot = 1;
to[++tot] = v;
to[++tot] = u;
}
int min(int a, int b) { return a < b ? a : b; }
int dfn[1000], low[1000];
bool bcut[1000];
void tarjan(int s, int f)
{
static int index;
int cnt = 0;
dfn[s] = low[s] = ++index;
for (int p = head[s]; p; p = next[p])
if (!dfn[to[p]])
{
tarjan(to[p], s);
low[s] = min(low[s], low[to[p]]);
++cnt;
if (low[to[p]] >= dfn[s] && f)
bcut[s] = true;
}
else
low[s] = min(low[s], dfn[to[p]]);
if (f && cnt > 1)
bcut[s] = true;
}
int main()
{
int n, m;
scanf("%d %d", &n, &m); //n节点m条连接（节点编号1-n）
for (int i = 0; i < m; ++i)
{
int u, v;
scanf("%d %d", &u, &v);
}
for (int i = 1; i <= n; i++)
{
if (!dfn[i])
tarjan(i, 0);
}
for (int i = 1; i <= n; ++i)
{
printf("Node %d: dfn:%d low:%d iscut:%d\n", i, dfn[i], low[i], bcut[i]);
}
return 0;
}

``````

• ### 将已知网络关键线路即桥定义为：删除此线路后，存在原网络中联通的节点，在新的网络中不连通

``````#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
{
static int tot = 1;
to[++tot] = v;
to[++tot] = u;
}
int min(int a, int b) { return a < b ? a : b; }
int dfn[1000], low[1000];
vector<pair<int, int>> br;
void tarjan(int s, int f)
{
static int index;
int cnt = 0;
dfn[s] = low[s] = ++index;
for (int p = head[s]; p; p = nxt[p])
if (!dfn[to[p]])
{
tarjan(to[p], s);
low[s] = min(low[s], low[to[p]]);
if (low[to[p]] > dfn[s])
br.push_back(s < to[p] ? make_pair(s, to[p]) : make_pair(to[p], s));
}
else if (to[p] != f)
low[s] = min(low[s], dfn[to[p]]);
}
int main()
{
int n, m;
scanf("%d%d", &n, &m); //n节点m条连接（节点编号1-n）
for (int i = 0; i < m; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i, 0);
sort(br.begin(), br.end());
for (int i = 0; i < br.size(); ++i)
printf("Bridge between Node %d and Node %d\n", br[i].first, br[i].second);
return 0;
}

``````

Looks like your connection to Dian was lost, please wait while we try to reconnect.