poj 1523 SPF（tarjan求割點）

本文出自   http://blog.csdn.net/shuangde800

------------------------------------------------------------------------------------------------

題目連結： poj-1523 

題意

   給一個連通的無向圖，求這個圖的所有割點，并且輸出各個割點和相連的邊去掉之後，會變成幾個連通分量

思路

   用tarjan求割點的基礎題，要求對tarjan算法的原理真正搞懂，這題就水了。

代碼

/**=====================================================
 *   This is a solution for ACM/ICPC problem
 *
 *   @source      : poj-1523 SPF
 *   @description : 圖的連通性-tarjan求割點
 *   @author      : shuangde
 *   @blog        : blog.csdn.net/shuangde800
 *   @email       : [email protected]
 *   Copyright (C) 2013/09/04 20:15 All rights reserved. 
 *======================================================*/
 
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
        
#include 
        
          #include 
         
           using namespace std; typedef long long int64; const int INF = 0x3f3f3f3f; const int MAXN = 1010; int n; bool ok; int cnt[MAXN]; namespace Adj { int size, head[MAXN]; struct Node { int v, next; }E[MAXN*2]; inline void initAdj() { size = 0; memset(head, -1, sizeof(head)); } inline void addEdge (int u, int v) { E[size].v = v; E[size].next = head[u]; head[u] = size++; } } using namespace Adj; namespace Tarjan { bool vis[MAXN]; int dfn[MAXN], low[MAXN], idx; inline void initTarjan() { idx = 1; memset(vis, 0, sizeof(vis)); memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); } void tarjan(int u) { vis[u] = true; dfn[u] = low[u] = idx++; for (int e = head[u]; e != -1; e = E[e].next) { int v = E[e].v; if (vis[v]) { low[u] = min(low[u], dfn[v]); } else { tarjan(v); low[u] = min(low[u], low[v]); if (u == 1) { ++cnt[u]; if (cnt[u] == 2) ok = true; } else if (low[v] >= dfn[u]) { ok = true; ++cnt[u]; } } } } } using namespace Tarjan; int main(){ int cas = 1; int u, v; while (~scanf("%d", &u) && u) { scanf("%d", &v); initAdj(); n = 0; n = max(n, max(u, v)); addEdge(u, v); addEdge(v, u); while (~scanf("%d", &u) && u) { scanf("%d", &v); n = max(n, max(u, v)); addEdge(u, v); addEdge(v, u); } if (cas != 1) puts(""); printf("Network #%d\n", cas++); memset(cnt, 0, sizeof(cnt)); ok = false; initTarjan(); tarjan(1); if (!ok) puts(" No SPF nodes"); else { if (cnt[1] > 1) printf(" SPF node %d leaves %d subnets\n", 1, cnt[1]); for (int i = 2; i <= n; ++i) { if (cnt[i]) printf(" SPF node %d leaves %d subnets\n", i, cnt[i] + 1); } } } return 0; }