首页 > 代码库 > POJ 1523 网络连通

POJ 1523 网络连通

2024-07-15 06:00:14   224人阅读

题目大意：

给你一个网络组，每台机子与其他机子的关系，让你找到所有的割点，如果没有割点，输出无

 

这道题目就是最直接的求割点问题，我在这里用的是邻接矩阵来存储机子之间的关系

割点问题的求解需要对深度优先搜索序数有比较好的理解

dfn[]用于存储当前的优先搜索序数，low[]存储当前点通过子节点或是回路所能达到的最小优先搜索序数

当（u，v）一组边dfn[u]<=low[v]时，那么u就是一个割点（这是u不作为树的顶点时的情况）

u作为顶点时，也即dfn[u]==1时，要看u的儿子节点数，大于等于2个时也说明它是割点

 

总体代码如下：

#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define N 1002#define min(a,b) a<b?a:b;#define max(a,b) a>b?a:b;int edge[N][N],low[N],dfn[N],subnets[N],son,visit[N],tmpdfn,n,flag;//flag标志这个图是否能找到割点void init(){    memset(visit,0,sizeof(visit));    memset(subnets,0,sizeof(subnets));    visit[1]=1,low[1]=1,dfn[1]=1,son=0,tmpdfn=1;}void dfs(int u)//dfs函数要进行递归，所以不在里面进行初始化操作{    for(int i=1;i<=n;i++){        if(edge[u][i]){            if(!visit[i]){                tmpdfn++;                visit[i]=1;                low[i]=dfn[i]=tmpdfn;                dfs(i);                low[u]=min(low[u],low[i]);//回退的时候，找祖先节点u能达到的较小的low值                if(low[i]>=dfn[u]){                    if(u!=1) subnets[u]++;                    else son++;                }            }            else low[u]=min(low[u],dfn[i]);//这时候i是u的祖先节点，且这是一条回边        }    }}int main(){    int u,v,cnt=0;    while(scanf("%d",&u)&&u!=0){        flag=0,n=0;        cnt++;//来统计网络个数        scanf("%d",&v);        n=max(n,u);        n=max(n,v);        memset(edge,0,sizeof(edge));        edge[u][v]=1,edge[v][u]=1;        while(scanf("%d",&u)&&u!=0){            scanf("%d",&v);            n=max(n,u);            n=max(n,v);            edge[u][v]=1,edge[v][u]=1;        }        printf("Network #%d\n",cnt);        init();        dfs(1);        if(son>1) subnets[1]=son-1;        for(int i=1;i<=n;i++){            if(subnets[i]){                flag=1;                printf("  SPF node %d leaves %d subnets\n",i,subnets[i]+1);            }        }        if(flag==0) printf("  No SPF nodes\n");        printf("\n");    }    return 0;}

 


联系
我们