程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1523 SPF (割頂 點雙連通分量)

POJ 1523 SPF (割頂 點雙連通分量)

編輯:C++入門知識

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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved