求無(wú)向連通圖的割點(diǎn)，使用Tarjan算法。
以下是我的代碼：
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(1007);
int n,m;
bool g[kMaxn][kMaxn];
int root,root_son,cnt,dfsn[kMaxn],low[kMaxn],subnet[kMaxn];
bool used[kMaxn];
void dfs(int u)
{
cnt++;
dfsn[u]=low[u]=cnt;
used[u]=true;
for(int v=1;v<=n;v++)
{
if(g[u][v])
{
if(!used[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfsn[u])
{
if(u!=root)
subnet[u]++;
else
root_son++;
}
}
else
low[u]=min(low[u],dfsn[v]);
}
}
}
void Tarjan()
{
root=n;
cnt=1;
root_son=0;
memset(used,false,kMaxn*sizeof(bool));
for(int i=1;i<=n;i++)
subnet[i]=1;
dfs(root);
if(root_son>1)
subnet[root]=root_son;
}
int main()
{
int T(0),u,v;
while(true)
{
n=0;
memset(g,false,kMaxn*kMaxn*sizeof(bool));
bool test(false);
while(scanf("%d",&u)==1)
{
if(u)
{
test=true;
scanf("%d",&v);
g[u][v]=g[v][u]=true;
n=max(n,max(u,v));
}
else
break;
}
if(!test)
break;
T++;
if(T!=1)
printf("\n");
printf("Network #%d\n",T);
Tarjan();
bool found(false);
for(int i=1;i<=n;i++)
if(subnet[i]>1)
{
found=true;
printf(" SPF node %d leaves %d subnets\n",i,subnet[i]);
}
if(!found)
printf(" No SPF nodes\n");
}
return 0;
}
posted on 2011-06-01 13:37
lee1r 閱讀(220)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
題目分類(lèi)：圖論