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

[eiclpy]

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

#include <cstdio>
int head[1000], to[100000], next[100000];
void addEdge(int u, int v)
{
	static int tot = 1;
	to[++tot] = v;
	next[tot] = head[u];
	head[u] = tot;
	to[++tot] = u;
	next[tot] = head[v];
	head[v] = tot;
}
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);
		addEdge(u, v); //编号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;
}

[eiclpy]

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

#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int head[1000], to[100000], nxt[100000];
void addEdge(int u, int v)
{
	static int tot = 1;
	to[++tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
	to[++tot] = u;
	nxt[tot] = head[v];
	head[v] = tot;
}
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);
		addEdge(u, v); //编号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;
}