http://poj.org/problem?id=1523

?

題意：? 求? 無向圖的 個點，以及 將個點 去掉后? 圖 被分成 幾個聯通塊；

?

題解：? tarjan ? 。

??1?#include<cstdio>
??2?#include<cstring>
??3?#include<cmath>
??4?#include<iostream>
??5?#include<algorithm>
??6?#include<set>
??7?#include<map>
??8?#include<queue>
??9?#include<vector>
?10?#include<string>
?11?#define?Min(a,b)?a<b?a:b
?12?#define?Max(a,b)?a>b?a:b
?13?#define?CL(a,num)?memset(a,num,sizeof(a));
?14?#define?eps??1e-6
?15?#define?inf?10001000
?16?
?17?#define?ll???__int64
?18?
?19?#define??read()??freopen("data.txt","r",stdin)?;
?20?#define?inf??9999999
?21?using?namespace?std;
?22?
?23?const?double?pi??=?acos(-1.0);
?24?const?int?maxn?=?1010;
?25?#define?N??30
?26?int?n?,?m?;
?27?int?dfn[maxn];//?記錄?入棧的次序；
?28?int?low[maxn];//?記錄?最小的?可以到達?的次序
?29?int?stack[maxn]?;//棧
?30?int??instack[maxn];//記錄?是否在棧中
?31?int?num?;//??入棧的次序
?32?int?top;??//?棧頂
?33?int??bcnt?;??//?所點的?代表?序號
?34?int?belong[maxn];//??記錄每個節點所屬?的?縮點號；
?35?vector<int>g[maxn]?;
?36?int?ans[maxn]?;
?37?int?in[maxn],out[maxn]?;
?38?void?tarjan(int?a)
?39?{
?40?????int?j?,i,?k;
?41?????dfn[a]?=?low[a]=?++num?;
?42?
?43?????stack[++top]?=?a;
?44?????instack[a]?=?1?;
?45?????for(i?=?0?;?i?<?g[a].size();i++)
?46?????{
?47?????????int?k?=?g[a][i]?;
?48?????????if(!dfn[k])
?49?????????{
?50?????????????tarjan(k)?;
?51?????????????if(low[a]?>?low[k])?low[a]?=?low[k]?;
?52?????????????if(?low[k]?>=?dfn[a])??ans[a]++?;//記錄 可以 分成的聯通塊數
?53?????????}
?54?????????else
?55?????????{
?56?????????????if(instack[k]?&&?dfn[k]?<?low[a])?low[a]?=?dfn[k]?;
?57?????????}
?58?
?59?????}
?60?
?61?
?62?
?63?}
?64?
?65?int??solve(int?root)
?66?{
?67?????int??i?,?j;
?68?????CL(instack,0);
?69?????CL(belong,0)?;
?70?????CL(dfn,0)?;
?71?????CL(low,0)?;
?72?????num?=?bcnt?=?top??=?0?;
?73?????tarjan(root);
?74?
?75?????if(bcnt?>?1)?return??0;
?76?????else?return??1??;
?77?}
?78?
?79?int??main()
?80?{
?81?????int?i?,a,b,t,j,mi,mx;
?82?????int?cas?=?0?;
?83?????//read()?;
?84?????while(scanf("%d",&a)!=EOF)
?85?????{
?86?
?87?????????if(a?==?0)?break;
?88?????????if(cas?>?0)printf("\n")?;
?89?
?90?
?91??????for(i?=?0;?i?<?maxn;i++)?g[i].clear()?;
?92?
?93??????scanf("%d",&b);
?94?
?95??????if(a?>?b)??mi?=?b;
?96??????else??mi?=?a;
?97?
?98??????if(a?>?b)?mx?=?a;
?99??????else?mx?=?b;
100??????g[a].push_back(b)?;
101??????g[b].push_back(a)?;
102?
103?????while(scanf("%d",&a)!=EOF)
104?????{
105?????????if(a?==?0)break??;
106?????????scanf("%d",&b);
107?????????g[a].push_back(b)?;
108?????????g[b].push_back(a)?;
109?
110?????????if(mi?>?a)?mi?=?a;
111?????????if(mi?>?b)?mi?=?b?;
112?
113?????????if(mx?<?a)?mx?=?a;
114?????????if(mx?<?b)?mx?=?b;
115?
116?
117?????}
118?????????//CL(in,0);
119?????????//CL(out,0)?;
120?????????CL(ans,0)?;
121?
122?
123?
124?????????solve(mi)?;
125?????????printf("Network?#%d\n",++cas)?;
126?
127?
128?????????ans[mi]?--?;// 因為 根沒有 入邊 ，所以 要減 1（ ，下面的 有加 1）
129??????????int?sum?=?0??;
130?????????for(i?=?mi?;i<=?mx;i++)
131?????????{
132?????????????//printf("%d?-------\n",low[i])?;
133????????????if(ans[i]?>?0)
134????????????{
135????????????????sum++?;
136????????????????printf("??SPF?node?%d?leaves?%d?subnets\n",i,ans[i]?+?1)?;
137????????????}
138?????????}
139?
140?
141?
142?????????if(sum?==?0)printf("??No?SPF?nodes\n");
143?
144?
145?????}
146?
147?
148?}

轉載于:https://www.cnblogs.com/acSzz/archive/2012/10/18/2729156.html

總結

以上是生活随笔為你收集整理的poj 1523 SPF (无向图 的 割点)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。