Network
A Telephone Line Company (TLC) is establishing a new telephone cable network. They are connecting several places numbered by integers from 1 to N . No two places have the same number. The lines are bidirectional and always connect together two places and in each place the lines end in a telephone exchange. There is one telephone exchange in each place. From each place it is possible to reach through lines every other place, however it need not be a direct connection, it can go through several exchanges. From time to time the power supply fails at a place and then the exchange does not operate. The officials from TLC realized that in such a case it can happen that besides the fact that the place with the failure is unreachable, this can also cause that some other places cannot connect to each other. In such a case we will say the place (where the failure occured) is critical. Now the officials are trying to write a program for finding the number of all such critical places. Help them.
Input
The input file consists of several blocks of lines. Each block describes one network. In the first line of each block there is the number of places N < 100. Each of the next at most N lines contains the number of a place followed by the numbers of some places to which there is a direct line from this place. These at most N lines completely describe the network, i.e., each direct connection of two places in the network is contained at least in one row. All numbers in one line are separated
by one space. Each block ends with a line containing just 0. The last block has only one line with N = 0;
Output
The output contains for each block except the last in the input file one line containing the number of critical places.
Sample Input
5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
0
Sample Output
1
2
Hint
You need to determine the end of one line.In order to make it's easy to determine,there are no extra blank before the end of each line.
Source
题目类型：割点数量
算法分析：直接使用Tarjan算法求出每个点的连通分量的个数，然后按照所得的结果判断每个节点是否是割点，注意要额外判断根节点的情况！！！
|
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 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits>() #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define i64 long long const int INF = 0x7FFFFFFF; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1000 + 66; //分别表示邻接矩阵、访问数组、dfs深度优先数、当前节点可以到达的最低优先数和每个节点的连通分量数(删去该节点) int edge[maxn][maxn], vis[maxn], dfsn[maxn], low[maxn], subnets[maxn]; int n, id;//分别表示节点总数和全局标志(标记dfs深度优先数) void Init (int rt) { for (int i = 0; i < maxn; i++)//初始化邻接矩阵 for (int j = 0; j < maxn; j++) { if (i == j) edge[i][j] = 0; else edge[i][j] = INF; } dfsn[rt] = low[rt] = id = 1;//将根节点的dfsn和low值都置为1 memset (vis, 0, sizeof (vis)); vis[rt] = 1;//初始化访问数组vis memset (subnets, 0, sizeof (subnets));//初始化连通分量数组subnets } void dfs (int u) { for (int v = 1; v <= n; v++)//依次判断所有的邻接点 { if (edge[u][v] < INF && u != v && !vis[v])//如果邻接且v为u的孩子节点 { vis[v] = 1; dfsn[v] = low[v] = ++id;//访问该孩子节点并打上标志 dfs (v);//递归地访问v的孩子节点 low[u] = min (low[u], low[v]);//使用u的孩子节点v的low值来更新u的low值 if (low[v] >= dfsn[u])//如果孩子节点的low值(深度)大于等于当前节点u的dfsn值(深度)，连通分量个数自加1 subnets[u]++; } else if (edge[u][v] < INF && u != v && vis[v])//如果邻接且v为u的祖先节点 low[u] = min (low[u], dfsn[v]);//直接使用回边中祖先节点的dfsn值更新u的low值即可 } } int main() { // CPPFF; while (cin >> n) { if (n == 0) break; Init(1); string s; getline (cin, s); while(getline(cin, s)) { stringstream ss (s); int a; ss >> a; if (a == 0) break; int b; while (ss >> b) { edge[a][b] = edge[b][a] = 1; } } dfs (1); int res = 0; for (int i = 1; i <= n; i++) { if (i == 1 && subnets[i] > 1) res++; else if (i != 1 && subnets[i]) res++; } cout << res << endl; } return 0; } |
- « 上一篇：poj1135
- poj1149：下一篇 »