心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
求无向连通图的割点,使用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 阅读(215) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理