POJ1523 SPF 【Tarjan求割点】

dzy posted @ 2013年6月30日 14:32 in POJ with tags POJ tarjan , 1848 阅读

理论知识看了好久的说、这里就不写了、

主要的是定义low[u]表示从u或u的子孙出发通过回边可以到达的最低深度优先数dfn[]。

low[u]=min{dfn[u], min{low[w]|w是u的子女}, min{dfn[v]|v与u邻接，且(u,v)是一条回边} }

?
POJ1523
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int low[2010],dfn[2010],ss[1010],v[1010],p[2010],n1[2010],h[1010],n,e=0,tot=0;
inline void ae(int a,int b){ p[e]=b; n1[e]=h[a]; h[a]=e++;}
void dfs(int u){
    for(int i=h[u];~i;i=n1[i]) if(!v[p[i]]){
        v[p[i]]=1;
        dfn[p[i]]=low[p[i]]=++tot;
        dfs(p[i]);
        low[u]=min(low[u],low[p[i]]);
        if(low[p[i]]>=dfn[u]) ss[u]++;
    }else low[u]=min(low[u],dfn[p[i]]);
}inline void init(){
    memset(h,-1,sizeof(h));
    memset(v,0,sizeof(v));
    memset(ss,0,sizeof(ss));
    e=0;tot=dfn[1]=low[1]=v[1]=1;
}int main(){
    int u,v,Tc=0;
    while(scanf("%d",&u),u){
        init();
        scanf("%d",&v);
        ae(u,v); ae(v,u);
        n=max(u,v);
        while(scanf("%d",&u),u){
            scanf("%d",&v);
            n=max(n,max(u,v));
            ae(u,v); ae(v,u);
        }dfs(1);
        if(Tc) printf("\n");
        printf("Network #%d\n",++Tc);
        int f=0;
        if(ss[1]>=1) ss[1]--;
        for(int i=1;i<=n;i++) if(ss[i]){
            f=1;
            printf("  SPF node %d leaves %d subnets\n",i,ss[i]+1);
        }if(!f) printf("  No SPF nodes\n");
    }return 0;
}

 

Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter