一家电话线公司(TLC)正在建立一个新的电话电缆网络。它们连接由1到N的整数编号的几个位置。没有两个地方的数字相同。这些线路是双向的,总是连接在两个地方,在每一个地方,线路都以电话交换机结束。每个地方都有一个电话交换机。从每个地方 可以通过其他地方的线路到达,但不需要直接连接,可以通过几个交换。有时,某个地方的电源出现故障,然后交换机无法运行。TLC的官员意识到,在这种情况下,除了故障地点无法到达之外,还可能导致其他一些地方无法相互连接。在这种情况下,我们将说出失败的地点发生)是关键的。现在,官员们正试图编写一个程序,找出所有这些关键地点的数量。帮助他们。
输入 输入文件由若干行组成。每个块描述一个网络。在每个区块的第一行中,有N<100的位置。接下来最多N行中的每一行都包含一个位置的编号,后面跟着一些位置的编号。这些最多N条线完全描述了网络,即网络中两个位置的每个直接连接至少包含在一行中。一行中的所有数字都是分开的 一个空格。每个块以仅包含0的行结束。最后一个块只有一条N=0的线; 输出 输出包含输入文件中除最后一个块外的每个块的一行,其中包含关键位置的数量。
Sample Input 5 5 1 2 3 4 0 6 2 1 3 5 4 6 2 0 0 Output 1 2
暗示 您需要确定一行的结尾。为了便于确定,在每行结尾之前没有多余的空格。
思路
用Tarjan算法求无向图的割点。如果u是割点,首先子节点v的追溯点要大于u的时间戳,如果u是根节点,还要满足该条件的子节点多于两个。
AC代码
#include <iostream>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <bitset>
#define AUTHOR "HEX9CF"
using namespace std;
const int maxn = 100005;
struct snode
{
int to;
int next;
} edge[maxn];
int head[maxn];
int cnt = 0;
int num = 0;
bitset<maxn> cut;
//tarjan
int dfn[maxn];// 时间戳
int low[maxn];// 追溯点
void init(){
num = 0;
cut.reset();
memset(head, -1, sizeof(head));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
}
void add(int u, int v)
{
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void print(int n)
{
for (int j = 1; j <= n; j++)
{
cout << j << "-";
for (int i = head[j]; ~i; i = edge[i].next)
{
cout << edge[i].to;
}
cout << endl;
}
}
// 求割点
void tarjan(int u, int root)
{
dfn[u] = low[u] = ++num; // 初始化节点
int son = 0;
for(int i = head[u]; ~i; i = edge[i].next){
int v = edge[i].to;// 访问子节点
if(!dfn[v]){
tarjan(v, u);
low[u] = min(low[u], low[v]);// 返回时更新
if(low[v] >= dfn[u]){
son++;
if(u != root || son > 1){// u不是根节点或有两个以上子节点满足条件
cut[u] = 1;
}
}
}else{
low[u] = min(low[u], dfn[v]);// 更新追溯点
}
// cout << u << " " << low[u] << endl;
}
}
int main()
{
int n;
int u, v;
string str;
stringstream ss;
while (1)
{
cin >> n;
getchar();
if (!n)
{
break;
}
init();
// 导入节点
while (1)
{
ss.clear();
getline(cin, str);
ss << str;
ss >> u;
if (!u)
{
break;
}
while (ss >> v)
{
add(u, v);
add(v, u);
}
}
// print(n);
for(int i = 1; i <= n; i++){
if(!dfn[i]){
tarjan(i, i);
}
}
cout << cut.count() << endl;
}
return 0;
}
标签:求无向,Tarjan,int,题解,head,dfn,maxn,low,include
From: https://blog.51cto.com/HEX9CF/8649418