POJ—1144 电话网络

题目描述

输入输出

输入样例

5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
0

输出样例

1
2

题意分析

题中的电话交换机就是图中的点,线路双向说明是个无向图.题中至关重要的点也就是图中的割点,一旦出现了问题影响的点也就会有许多个.所以这个题主要是求割点的个数.

参考代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn = 105;
int n, root;
int head[maxn], cnt;
struct Edge {
	int to, next;
}e[maxn*maxn];
int low[maxn], dfn[maxn], num;
bool cut[maxn];//标记是否是割点
void add(int u, int v)
{
	e[++cnt].next = head[u];//把当前节点插入到head之后
	e[cnt].to = v;//修改新增节点的to值
	head[u] = cnt;//head中存放新增边结点的索引.
}//e的索引从1开始的,星图中且最后一个临界点的next值为0.

void tarjan(int u)
{
	dfn[u] = low[u] = ++num;
	int flag = 0;
	for (int i = head[u]; i; i = e[i].next)//如果最后i=0则说明,临界点已遍历完毕
	{
		int v = e[i].to;
		if (!dfn[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if (low[v] >= dfn[u])
			{
				flag++;//符合割点条件的临界点的个数
				if (u != root || flag > 1)//如果非根且满足子节点low>父节点dfn,或是根且满足子节点low>根节点dfn个数>=2  则为割点.
				{
					cut[u] = true;//是割点
				}
			}
		}
		else {
			low[u] = min(low[u], dfn[v]);//已经遍历过则直接更新父节点u的值..
		}
	}
}

void init()//数组的更新
{
	memset(head, 0, sizeof(head));
	memset(low, 0, sizeof(low));
	memset(dfn, 0, sizeof(dfn));
	memset(cut, false, sizeof(cut));
	cnt = num = 0;
}

int main()
{
	while (cin >> n && n)//控制case
	{
		init();
		int u, v;
		while (cin >> u && u)//控制每个case
		{
			while (true)
			{
				char c = getchar();//每次获取空格
				if (c == '\n')
				{
					break;
				}
				cin >> v;
				add(u, v);
				add(v, u);

			}

		}
		for (int i = 1; i <= n; i++)//判断每个节点
		{
			if (!dfn[i])
			{
				root = i;
				tarjan(i);
			}
		}
		int ans = 0;//统计割点
		for (int i = 0; i <= n; i++)
		{
			if (cut[i])
			{
				ans++;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

题目考点

1. Tarjan求割点的使用
2. 脸是双向星的使用.