POJ-1523 SPF 割点

本文主要是介绍POJ-1523 SPF 割点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你幅图，求割点 对每个点去掉后联通分量数；

裸Tarjan

#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 1025;
const int inf = 1<<29;
int n,son;
vector<int>map[maxn];
int dfs_clock,low[maxn],dfn[maxn];
int iscut[maxn];
void dfs( int u,int fa )
{low[u] = dfn[u] = ++dfs_clock;for( int i = 0; i < map[u].size(); i ++ ){int v = map[u][i];if( !dfn[ v ] ){dfs(v,u);low[u] = low[u] <= low[v] ? low[u]:low[v];if( low[v] >= dfn[u] ){if( fa != -1 )iscut[u] ++;elseson ++;}}else if( dfn[v] < dfn[u] && v != fa )  low[u] = low[u] <= dfn[v] ? low[u]:dfn[v];  }
}
void tarjan()
{dfs_clock = 0,son = 0;memset( low,0,sizeof(low) );  memset( dfn,0,sizeof(dfn) );  memset( iscut,0,sizeof(iscut) );dfs(1,-1);if( son > 1 )iscut[1] = son - 1;}
int main()
{//freopen("data.txt","r",stdin);int cas = 0,u,v;while( scanf("%d",&u) != EOF,u ){scanf("%d",&v);for( int i = 1; i <= 1000; i ++ )  map[i].clear();  map[u].push_back( v );map[v].push_back( u );n = u >= v?u:v;while( scanf("%d",&u) == 1 && u ){scanf("%d",&v);map[u].push_back( v );map[v].push_back( u );n = u >= v?u:v;}tarjan();int flag = 0;if( cas )	puts("");printf("Network #%d\n",++cas);for( int i = 1; i <= n; i ++ ){if( iscut[i] ){flag = 1;printf("  SPF node %d leaves %d subnets\n",i,iscut[i]+1);}}if( !flag )printf("  No SPF nodes\n");}return 0;
}

这篇关于POJ-1523 SPF 割点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---