08月
06

UVA-315 Network

发表于 • 本文总阅读数 次
字数统计: 352

题目

  https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=251

题意

  给出一张无向图，求图中割点的个数。割点是指删除该点后，其他点之间的连通性会受到影响的点。

题目解析

  用tarjan算法来解决，这题的输入有点麻烦，因为输入的问题runtime error了好几次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/* https://cn.vjudge.net/contest/67418#problem/B */
#include <stdio.h>
#include <string.h>
#define min(a, b) (a < b) ? a : b

const int MAX_N = 100 + 10;

int n;
int mp[MAX_N][MAX_N];
int vis[MAX_N], vis_n;
int low[MAX_N];
int is_ctp[MAX_N];

void tarjan(int v, int root)
{
	int i, child = 0;

	vis[v] = vis_n;
	low[v] = vis_n;
	vis_n++;
	for(i = 1; i <= n; i++)
	{
		if(mp[v][i] != 0)
		{
			if(vis[i] == -1)
			{
				tarjan(i, root);
				low[v] = min(low[v], low[i]);
				if(v == root)
				{
					child++;
				}
				else if(low[i] >= vis[v])
				{
					is_ctp[v] = 1;
				}
			}
			else
			{
				low[v] = min(low[v], vis[i]);
			}
		}
	}
	if(v == root && child >= 2)
	{
		is_ctp[root] = true;
	}
}

int main()
{
	int i, a, b, ans;
	char ch;

	while(scanf("%d", &n) != EOF && n != 0)
	{
		memset(mp, 0, sizeof(mp));
		while(scanf("%d", &a) != EOF && a != 0)
		{
			while(getchar() != '\n')
			{
				scanf("%d", &b);
				mp[a][b] = 1;
				mp[b][a] = 1;
			}
		}

		memset(vis, -1, sizeof(vis));
		memset(is_ctp, 0, sizeof(is_ctp));
		for(i = 1; i <= n; i++)
		{
			if(vis[i] == -1)
			{
				vis_n = 1;
				tarjan(i, i);
			}
		}
		ans = 0;
		for(i = 1; i <= n; i++)
		{
			if(is_ctp[i] == 1)
			{
				ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}
分享到：
0%