<題目鏈接>
<轉載于 >>> >
題目大意：
給你一個圖，讓你判斷他是不是仙人掌圖。
仙人掌53的個人主頁，仙人掌圖的條件是：
1、是強連通圖。
2、每條邊在仙人掌圖中只屬于一個強連通分量。仙人掌圖pdf說明>>>
解題分析：
1、首先得先熟練掌握tarjan算法的應用。
仙人球生命力頑強嗎，2、必須了解仙人掌圖的三個性質：
（1）.仙人掌dfs圖中不能有橫向邊，簡單的理解為每個點只能出現在一個強聯通分量中。
（2）.low[v]<dfn[u],其中u為v的父節點
（3）.a[u]+b[u]<2 ， ?a[u]為u節點的兒子節點中有a[u]個low值小于u的dfn值。b[u]為u的逆向邊條數。
三個性質有一個不滿足則不是仙人掌圖。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 #define rep(i,s,t) for(int i=s;i<=t;i++) 7 #define clr(a,b) memset(a,b,sizeof(a)) 8 const int N = 2e4+10; 9 const int M = 5e4+10; 10 int head[N],dfn[N],low[N],belong[N],stk[N]; 11 bool color[N],instk[N],ok; 12 int n,top,tot,index,scnt; 13 struct Edge{ 14 int to,next; 15 }edge[M]; 16 void init(){ 17 tot=top=index=scnt=0; 18 clr(head,-1);clr(dfn,0);clr(low,0);clr(belong,0); 19 clr(stk,0);clr(instk,false);clr(color,false); 20 } 21 void addedge(int u,int v){ 22 edge[tot].to=v,edge[tot].next=head[u]; 23 head[u]=tot++; 24 } 25 void Tarjan(int u){ 26 dfn[u]=low[u]=++index; 27 stk[++top]=u,instk[u]=true; 28 int cnt=0; 29 for(int i=head[u];~i;i=edge[i].next){ 30 int v = edge[i].to; 31 if(color[v])ok=false; //性質1 32 if(!dfn[v]){ 33 Tarjan(v); 34 if(low[v]>dfn[u])ok=false; //性質2 35 if(low[v]<dfn[u])cnt++; //u的子節點中low值小于dfn[u]值得個數 36 if(cnt==2)ok=false; 37 low[u]=min(low[u],low[v]); 38 }else if(instk[v]){ 39 low[u]=min(low[u],dfn[v]);cnt++; 40 if(cnt==2)ok=false; //性質3 41 } 42 } 43 if(dfn[u]==low[u]){ 44 scnt++; 45 while(true){ 46 int v=stk[top--]; 47 instk[v]=false; 48 belong[v]=scnt; 49 if(v==u)break; 50 } 51 } 52 color[u]=true; 53 } 54 int main(){ 55 int T;scanf("%d",&T);while(T--){ 56 scanf("%d",&n); 57 init(); 58 int u,v;while(scanf("%d%d",&u,&v),u||v){ 59 u++,v++; 60 addedge(u,v); 61 } 62 ok=true; 63 rep(i,1,n) if(!dfn[i]) { 64 Tarjan(i); 65 } 66 printf((scnt==1&&ok==true)?"YES\n":"NO\n"); 67 } 68 }
仙人掌頑強堅強的象征作文？?
?
2018-12-06
