176
Poj 1523 SPF 關節點
經典的關節點例題，要注意隻有1個點的情況
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int org[1001][1001],n;
bool ok;
int dph[1001],low[1001],vis[1001],Ans[1001];
void dfs(int u,int d)//Tarjan
{
dph[u]=low[u]=d;
vis[u]=1;
int ans=0;
for(int v=1;v<=n;v++)
{
if(!org[u][v])continue;
if(vis[v])
{
low[u]=min(low[u],dph[v]);
}
else
{
dfs(v,d+1);
if(low[v]>=dph[u])ans++;
low[u]=min(low[u],low[v]);
}
}
if(u==1&&ans>=1)Ans[u]=ans-1;
else Ans[u]=ans;
}
int main()
{
int a,b,T=0;
while(~scanf("%d",&a)&&a)
{
n=0;
scanf("%d",&b);
memset(org,0,sizeof(org));
if(T)puts("");
T++;
org[a][b]=org[b][a]=1;
n=max(n,max(a,b));
while(~scanf("%d",&a)&&a)
{
scanf("%d",&b);
org[a][b]=org[b][a]=1;
n=max(n,max(a,b));
}
ok=0;
memset(Ans,0,sizeof(Ans));
memset(vis,0,sizeof(vis));
printf("Network #%d\n",T);
dfs(1,1);
for(int i=1;i<=n;i++)
{
if(Ans[i])
ok=1,
printf(" SPF node %d leaves %d subnets\n",i,Ans[i]+1);
}
if(!ok)printf(" No SPF nodes\n");
}
}
最後更新：2017-04-03 16:48:54