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



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

    #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;
    }
    
    


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

    #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;
    }
    
    

 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

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