poj 1523 spf 求割點

無向圖求割點的模版題。就是對tarjan的運用。

 [cpp]
#include <iostream>  
#include <cstdio>  
#include <cstring>  
using namespace std; 
const int maxn=1e3+9,N=1e3; 
bool e[maxn][maxn]; 
int dfn[maxn],low[maxn],count,in[maxn]; 
 
 
void tarjan(int t,int from) 
{ 
    dfn[t]=low[t]=++count; 
    int ret=0; 
    for(int i=1;i<=N;i++) 
    if(e[t][i]) 
    { 
        if(i==from) continue; 
        if(dfn[i]==-1) 
        { 
            ret++; 
            tarjan(i,t); 
            low[t]=min(low[t],low[i]); 
            if(low[i]>=dfn[t]) 
            in[t]++; 
        } 
        else 
        { 
            low[t]=min(low[t],dfn[i]); 
        } 
    } 
    if(t==from) 
    in[t]=ret-1; 
} 
 
 
 
 
int main() 
{ 
//    freopen("in.txt","r",stdin);  
    int from,to,tcase=0; 
    while(scanf("%d",&from),from) 
    { 
        scanf("%d",&to); 
        e[from][to]=1; 
        e[to][from]=1; 
        while(scanf("%d",&from),from) 
        { 
            scanf("%d",&to); 
            e[from][to]=1; 
            e[to][from]=1; 
        } 
 
 
//        printf("hi");  
 
 
        count=0; 
        memset(dfn,-1,sizeof(dfn)); 
        memset(in,0,sizeof(in)); 
        for(int i=1;i<=N;i++) 
        if(dfn[i]==-1) 
        tarjan(i,i); 
 
 
        printf("Network #%d\n",++tcase); 
        int cnt=0; 
        for(int i=1;i<=N;i++) 
        { 
            if(in[i]>0) 
            { 
                printf("  SPF node %d leaves %d subnets\n",i,in[i]+1); 
                cnt++; 
            } 
        } 
        if(!cnt) 
        printf("  No SPF nodes\n"); 
        memset(e,0,sizeof(e)); 
        printf("\n"); 
    } 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e3+9,N=1e3;
bool e[maxn][maxn];
int dfn[maxn],low[maxn],count,in[maxn];

void tarjan(int t,int from)
{
    dfn[t]=low[t]=++count;
    int ret=0;
    for(int i=1;i<=N;i++)
    if(e[t][i])
    {
        if(i==from) continue;
        if(dfn[i]==-1)
        {
            ret++;
            tarjan(i,t);
            low[t]=min(low[t],low[i]);
            if(low[i]>=dfn[t])
            in[t]++;
        }
        else
        {
            low[t]=min(low[t],dfn[i]);
        }
    }
    if(t==from)
    in[t]=ret-1;
}

int main()
{
//    freopen("in.txt","r",stdin);
    int from,to,tcase=0;
    while(scanf("%d",&from),from)
    {
        scanf("%d",&to);
        e[from][to]=1;
        e[to][from]=1;
        while(scanf("%d",&from),from)
        {
            scanf("%d",&to);
            e[from][to]=1;
            e[to][from]=1;
        }

//        printf("hi");

        count=0;
        memset(dfn,-1,sizeof(dfn));
        memset(in,0,sizeof(in));
        for(int i=1;i<=N;i++)
        if(dfn[i]==-1)
        tarjan(i,i);

        printf("Network #%d\n",++tcase);
        int cnt=0;
        for(int i=1;i<=N;i++)
        {
            if(in[i]>0)
            {
                printf("  SPF node %d leaves %d subnets\n",i,in[i]+1);
                cnt++;
            }
        }
        if(!cnt)
        printf("  No SPF nodes\n");
        memset(e,0,sizeof(e));
        printf("\n");
    }
    return 0;
}