Description
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.
表示英语看不懂
不过还好有那么一个ppt。题意为求一个图上是否有割点，如果有，依次输出每个割点，并输出这个割点没有时会形成的块的个数。tarjan一下，low[son]>=deep[father]的f[father]++，就可以了。然后需要特判一下根节点，要是根只有一个枝的话，就不是割点，（并不是有两个son，因为可能有样例2这种情况，所以只要f[root]--，再正常做就可以了）。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n,test;
bool flag;
int h[1010],nxt[1010],to[1010];
int deep[1010],low[1010],f[1010];
int cnt,tot;
void clear()
{
cnt=tot=flag=0;
memset(deep,0,sizeof(deep));
memset(low,0,sizeof(low));
memset(h,-1,sizeof(h));
}
void add(int x,int y)
{
to[cnt]=y;
nxt[cnt]=h[x];
h[x]=cnt;
cnt++;
}
void insert(int x,int y)
{
add(x,y);add(y,x);
}
void tarjan(int x)
{
low[x]=deep[x]=++tot;
for(int i=h[x];i!=-1;i=nxt[i])
{
if(!deep[to[i]])
{
tarjan(to[i]);
low[x]=min(low[x],low[to[i]]);
if(deep[x]<=low[to[i]]) f[x]++;
}
else low[x]=min(low[x],deep[to[i]]);
}
}
int main()
{
int x,y;
while(scanf("%d",&x))
{
if(x==0) break;
clear();scanf("%d",&y);
n=max(max(x,y),n);insert(x,y);
while(scanf("%d",&x)&&x)
{
scanf("%d",&y);
n=max(max(x,y),n);insert(x,y);
}
for(int i=2;i<=n;i++)
f[i]=1;
f[1]=0;
tarjan(1);
printf("Network #%d\n",++test);
for(int i=1;i<=n;i++)
if(f[i]>1)
{
printf(" SPF node %d leaves %d subnets\n",i,f[i]);
flag=1;
}
if(!flag)printf(" No SPF nodes\n");
puts("");
}
return 0;
}