題意: 判斷是不是強(qiáng)連通圖 ,同時(shí)每一條邊必須只能在一個(gè)環(huán)里

思路:之前我的強(qiáng)連通用的全是雙深搜,結(jié)果題目的第二個(gè)要求很難判斷,一開(kāi)始寫(xiě)了三個(gè)深搜加上并查集,結(jié)果越寫(xiě)越亂,其實(shí)就是在判斷一個(gè)邊是否只在一個(gè)環(huán)內(nèi)搞不定,后來(lái)看了下網(wǎng)上的代碼,用的全是tarjan,沒(méi)辦法了,又學(xué)習(xí)了一下tarjan算法,學(xué)完后發(fā)現(xiàn)這個(gè)算法不錯(cuò),比雙深搜快一倍的時(shí)間吧,他的時(shí)間復(fù)雜度是O(n + m) n是點(diǎn)m是邊,tarjan算法的運(yùn)行步驟為第二問(wèn)的解決提供了條件,其中的stack,low,dfn配合的很好,我們要開(kāi)一個(gè)數(shù)組記錄搜索路徑,然后當(dāng)我們搜到一個(gè)點(diǎn)發(fā)現(xiàn)他被搜過(guò)同時(shí)他還在stack中的話(huà),我們直接通過(guò)路徑數(shù)組原路返回到他,把路上所有的點(diǎn)的次數(shù)都加1(開(kāi)個(gè)數(shù)組記錄次數(shù)),如果發(fā)現(xiàn)有大于1的直接就NO了,還有就是點(diǎn)有一個(gè)點(diǎn)的次數(shù)不要加1,就是查找路徑的第一個(gè)點(diǎn)的上一個(gè)點(diǎn),也是路徑中的最后一個(gè)點(diǎn)(因?yàn)槭黔h(huán)),這樣就ok了.

#include<stdio.h>
#include<string.h>
#include<stack>
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
#define N_node 25000 + 1000
#define N_edge 55000 + 1000


using namespace std;


typedef struct
{
? ?int to ,next;
}STAR;


STAR E[N_edge];
int list[N_node] ,tot;
int mer[N_node];
int count[N_node];
int DFN[N_node] ,LOW[N_node];
int Index ,num ,okk;
int instack[N_node];
stack<int>st;?


void add(int a ,int b)
{
? ?E[++tot].to = b;
? ?E[tot].next = list[a];
? ?list[a] = tot;
}


int minn(int x ,int y)
{
? ?return x < y ? x : y;
}


void merge(int e ,int s)
{
? ?while(mer[s] != e)
? ?{
? ? ? count[s] ++;
? ? ? if(count[s] >= 2)
? ? ? {
? ? ? ? ?okk = 1;
? ? ? ? ?return ;
? ? ? }
? ? ? s = mer[s];
? ?}
}


void Tarjan(int s)
{
? ?if(okk) return;
? ?DFN[s] = LOW[s] = ?Index ++;
? ?st.push(s);
? ?instack[s] = 1;
? ?for(int k = list[s] ;k ;k = E[k].next)
? ?{
? ? ? int to = E[k].to;
? ? ? if(!DFN[to])
? ? ? {
? ? ? ? ?mer[to] = s;
? ? ? ? ?Tarjan(to);
? ? ? ? ?LOW[s] = minn(LOW[to] ,LOW[s]);
? ? ? }
? ? ? else if(instack[to])
? ? ? {
? ? ? ? ?LOW[s] = minn(DFN[to] ,LOW[s]);
? ? ? ? ?merge(to ,s);
? ? ? ? ?if(okk) return; ? ? ??
? ? ? }
? ?}
? ?if(LOW[s] == DFN[s])
? ?{
? ? ? num ++;
? ? ? if(num > 1) okk = 1; ??
? ? ? while(1)
? ? ? {
? ? ? ? ?int v = st.top();
? ? ? ? ?st.pop();
? ? ? ? ?instack[v] = 0;
? ? ? ? ?if(v == s) break;
? ? ? }
? ?}
? ?return ;
}
?
int main ()
{
? ?int t ,i ,n ,a ,b;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? scanf("%d" ,&n);
? ? ? memset(list ,0 ,sizeof(list));
? ? ? memset(instack ,0 ,sizeof(instack));
? ? ? memset(DFN ,0 ,sizeof(DFN));
? ? ? memset(LOW ,0 ,sizeof(LOW));
? ? ? memset(count ,0 ,sizeof(count));
? ? ? for(i = 0 ;i < n ;i ++)mer[i] = i;
? ? ? while(!st.empty()) st.pop();
? ? ? tot = Index = 1 ,num = 0;
? ? ? while(scanf("%d %d" ,&a ,&b) && a + b)
? ? ? {
? ? ? ? ?add(a ,b);
? ? ? }
? ? ? okk = 0;
? ? ? for(i = 0 ;i < n ;i ++)
? ? ? {
? ? ? ? ?if(okk) break;
? ? ? ? ?if(DFN[i]) continue;
? ? ? ? ?Tarjan(i);
? ? ? }
? ? ? if(okk) printf("NO\n");
? ? ? else printf("YES\n");
? ?}
? ?return 0;
}
? ? ??
? ? ? ? ?
? ? ? ? ?

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的hdu3594 强连通 tarjan的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。