SPF Zoj 1119 tarjan求割点数量
描述
Consider the two networks shown below. Assuming that data moves around these networks only between directly connected nodes on a peer-to-peer basis, a failure of a single node, 3, in the network on the left would prevent some of the still available nodes from communicating with each other. Nodes 1 and 2 could still communicate with each other as could nodes 4 and 5, but communication between any other pairs of nodes would no longer be possible.
Node 3 is therefore a Single Point of Failure (SPF) for this network. Strictly, an SPF will be defined as any node that, if unavailable, would prevent at least one pair of available nodes from being able to communicate on what was previously a fully connected network. Note that the network on the right has no such node; there is no SPF in the network. At least two machines must fail before there are any pairs of available nodes which cannot communicate.
输入
The input will contain the description of several networks. A network description will consist of pairs of integers, one pair per line, that identify connected nodes. Ordering of the pairs is irrelevant; 1 2 and 2 1 specify the same connection. All node numbers will range from 1 to 1000. A line containing a single zero ends the list of connected nodes. An empty network description flags the end of the input. Blank lines in the input file should be ignored.
输出
For each network in the input, you will output its number in the file, followed by a list of any SPF nodes that exist.
The first network in the file should be identified as "Network #1", the second as "Network #2", etc. For each SPF node, output a line, formatted as shown in the examples below, that identifies the node and the number of fully connected subnets that remain when that node fails. If the network has no SPF nodes, simply output the text "No SPF nodes" instead of a list of SPF nodes.
样例输入
1 2
5 4
3 1
3 2
3 4
3 5
0
1 2
2 3
3 4
4 5
5 1
0
1 2
2 3
3 4
4 6
6 3
2 5
5 1
0
0
样例输出
Network #1
SPF node 3 leaves 2 subnets
Network #2
No SPF nodes
Network #3
SPF node 2 leaves 2 subnets
SPF node 3 leaves 2 subnets
大意:给出一个无向连通图，让你求出割点的数量
分析:从1开始dfs产生深度优先生成树，对于无向图而言，只有生成树的边和回边，在生成树中u为关节点的充要条件如下：
1，如果顶点u是生成树的根，则u至少有两个子女。
2，如果u不是生成树的根，则保证u的子女w的 low(w) >= dfn(u)
（dfn和low的值均在搜索过程中产生
代码如下:
#include<bits/stdc++.h>
using namespace std;
int Edge[1001][1001];
int visited[1001];//代表这个点是否被访问过
int nodes;
int tmpdfn;
int dfn[1001];
int low[1001];
int son;
int subnets[1001];//表示去掉u时产生的联通分量的个数
void init() {
low[1] = dfn[1] = 1;
tmpdfn = 1;son = 0;
memset(visited,0,sizeof(visited));
visited[1] = 1;
memset(subnets,0,sizeof(subnets));
}
void dfs(int u) {
for(int v = 1;v <= nodes;v++) {
if(Edge[u][v]) {
//v和u邻接
//1，v是u的祖先 则(u,v)是一条回边 2，v是u的儿子节点
if(!visited[v]) {//v未访问,第二种情况
visited[v] = 1;
tmpdfn++;
dfn[v] = low[v] = tmpdfn;
dfs(v);//结束时 真正的low[v]已经求出
low[u] = min(low[u],low[v]);//回退的时候求出u的low值
if(low[v] >= dfn[u]) {
if(u != 1) subnets[u]++;
if(u == 1) son++;//根的情况
}
}
else low[u] = min(low[u],dfn[v]);
}
}
}
int main() {
int u,v;
int find;
int number = 1;
for(;;) {
scanf("%d",&u);
if(u == 0) break;
memset(Edge,0,sizeof(Edge));
nodes = 0;
scanf("%d",&v);
if(u>nodes) nodes = u;
if(v>nodes) nodes = v;
Edge[u][v] = Edge[v][u] = 1;
while(1) {
scanf("%d",&u);
if(u == 0) break;
scanf("%d",&v);
if(u>nodes) nodes = u;
if(v>nodes) nodes = v;
Edge[u][v] = Edge[v][u] = 1;
}
if(number > 1) printf("
");
printf("Network #%d
",number++);
init();
dfs(1);
if(son > 1) subnets[1] = son - 1;
find = 0;
for(int i = 1;i <= nodes;i++) {
if(subnets[i]) {
find = 1;
printf(" SPF node %d leaves %d subnets
",i,subnets[i]+1);
}
}
if(!find) printf(" No SPF nodes
");
}
return 0;
}
附加:
其实在dfs遍历的过程中就可以将图的重联通分量求出
思路：建立一个栈，储存当前重连通分量，在dfs的过程中，每找到一条生成树的边或回边，就把这条边加入栈中，如果遇到某个顶点u是一个割点，同时把边从栈顶一条条取出，直到遇到了边(u,v)，取出的这些边和与其关联的顶点，组成一个重连通分量。割点可以属于多个重连通分量，其余顶点和每条边只属于一个重连通分量。
实现代码如下:
#include<bits/stdc++.h>
using namespace std;
#define MAXN 20
#define MAXM 40
struct edge {
int u,v;
edge(int u,int v):u(u),v(v){}
void output() {printf("%d-%d",u,v);}
int comp(edge& t) {return ((t.u == u && t.v == v) || (t.u == v && t.v == u));}
};
edge edges[MAXM];//栈
int se;//栈顶
int Edge[MAXN][MAXN];
int visited[MAXN];
int n,m;
int tt;
int dfn[MAXN];
int low[MAXN];
void dfs(int u) {
for(int v = 1;v<=n;v++) {
if(Edge[u][v] == 1) {
edge t(u,v);edges[++se] = t;
Edge[u][v] = Edge[v][u] = 2;
if(!visited[v]) {
visited[v] = 1;
tt++;dfn[v] = low[v] = tt;
dfs(v);
low[u] = min(low[u],low[v]);
if(low[v] >= dfn[u]) {
bool firstedge = true;
while(1) {
if(se<0) break;
if(firstedge) firstedge = false;
else printf(" ");
edge t1;
t1 = edges[se];
t1.output();
edge[se].u = edge[se].v = 0;
se--;
if(t1.comp(t)) break;
}
printf("
");
}
}
else low[u] = min(low[u],dfn[v]);
}
}
}
int main() {
int u,v;
int number = 1;
for(;;) {
scanf("%d%d",&u,&v);
if(n == 0 && m == 0) break;
memset(Edge,0,sizeof(Edge));
for(int i = 1;i<=m;i++) {
scanf("%d%d",&u,&v);
Edge[u][v] = Edge[v][u] = 1;
}
if(number>1) printf("
");
number++;
low[1] = dfn[1] = 1;
tt = 1;
memset(visited,0,sizeof(visited));
visited[1] = 1;
memset(edges,0,sizeof(edges));
se = -1;
dfs(1);
}
return 0;
}