POJ 1523 SPF （割頂 點雙連通分量）
題意就是求出在一個圖上去除一個點之後，那個圖會變成多少個子連通圖。
顯然我們要求出割頂。我的代碼套用了劉汝佳的大白書的tarjan算法，用一個數組cnt[]記錄一個點是多少個點雙連通分量的割頂。當發現一個點是割頂的時候，就cnt[i]++。最後，如果一個點是一棵dfs樹的樹根時，就輸出cnt[i],否則就輸出cnt[i]+1（因為那個點有父親，而cnt數組記錄的相當於是該點的兒子個數）。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Edge
{
int u,v;
Edge(int uu,int vv)
{
u=uu;v=vv;
}
Edge(){}
};
const int maxn=1005;
int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;
vectorG[maxn],bcc[maxn];
vector > ans;
int cnt[maxn];
bool isfa[maxn];
stacks;
int dfs(int u,int fa)
{
int lowu=pre[u]=++dfs_clock;
int child=0;
for(int i=0;i=pre[u])
{
iscut[u]=true;cnt[u]++;
bcc_cnt++;bcc[bcc_cnt].clear();
for(;;)
{
Edge x=s.top();s.pop();
if(bccno[x.u]!=bcc_cnt){bcc[bcc_cnt].push_back(x.u);bccno[x.u]=bcc_cnt;}
if(bccno[x.v]!=bcc_cnt){bcc[bcc_cnt].push_back(x.v);bccno[x.v]=bcc_cnt;}
if(x.u==u&&x.v==v) break;
}
}
}
else if(pre[v]maxed) maxed=u;
scanf("%d",&v);
if(v>maxed) maxed=v;
valid=true;
u--,v--;
G[u].push_back(v);
G[v].push_back(u);
}
else {flag=false;break;}
}
if(!flag) break;
if(valid==false) break;
find_bcc(maxed);
bool hascut=false;
for(int i=0;i<maxed;i++) {="" if(iscut[i])="" hascut="true;" if(!isfa[i])ans.push_back(make_pair(i+1,cnt[i]+1));="" else="" ans.push_back(make_pair(i+1,cnt[i]));="" }="" cas++;="" printf("network="" #%d\n",cas);="" if(!hascut)="" printf("="" no="" spf="" nodes\n");="" for(int="" i="0;i
