poj 1523 spf割点を求める

1735 ワード

カットポイントを求めるテンプレートの問題がありません.tarjanの運用です.
#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
",++tcase); int cnt=0; for(int i=1;i<=N;i++) { if(in[i]>0) { printf(" SPF node %d leaves %d subnets
",i,in[i]+1); cnt++; } } if(!cnt) printf(" No SPF nodes
"); memset(e,0,sizeof(e)); printf("
"); } return 0; }