HDU 1269

題意：n個(gè)點(diǎn)m條單向邊，問(wèn)任意兩個(gè)點(diǎn)是否連通。

總結(jié)：參考大神博客碼的，有些地方還是不太明白。 而且這題還可以雙向dfs做，有時(shí)間再做一下。

// HDU-1269 #include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define F(i,a,b) for (int i=a;i<b;i++) #define FF(i,a,b) for (int i=a;i<=b;i++) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 1e4+10, M = 1e5+10;int n, m, sum, top, tot; //sum為強(qiáng)連通分量數(shù)，top為棧指針 int head[N], Stack[N], instack[N]; //Stack[]為模擬棧，instack[]表示是否在棧中 int dfn[N], low[N], Belong[N]; //dfn[]為深搜次序數(shù)組，Low[u]為u結(jié)點(diǎn)或者u的子樹(shù)結(jié)點(diǎn)所能追溯到的最早棧中結(jié)點(diǎn)的次序號(hào)，這兩個(gè)數(shù)組是關(guān)鍵。Belong[]表示每個(gè)結(jié)點(diǎn)所對(duì)應(yīng)的強(qiáng)連通分量標(biāo)號(hào)數(shù)組，這個(gè)題里用不到 struct Edge { int to, next; } edge[M];void Init() {sum=top=tot=0;mes(head, -1);mes(dfn, 0); } void Addedge(int u, int v) {edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++; } void Tarjan(int u) //Tarjan算法求有向圖的強(qiáng)連通分量 {dfn[u]=low[u]=++tot; //時(shí)間戳，不太明白Stack[top++]=u, instack[u]=1;for(int e=head[u]; e!=-1; e=edge[e].next) {int v=edge[e].to;if(dfn[v]==0) {Tarjan(v);if(low[u]>low[v]) low[u]=low[v]; //更新結(jié)點(diǎn)v所能到達(dá)的最小次數(shù)層，這里不太明白 }else if(instack[v] && low[u]>dfn[v]) {low[u]=dfn[v];}}if(dfn[u]==low[u]) { //如果節(jié)點(diǎn)v是強(qiáng)連通分量的根 sum++;while(top!=0) {int t=Stack[--top];instack[t]=0;Belong[t]=sum;if(t==u) break; //直到將v從棧中退出，這不太明白 }} } void Solve() {FF(i,1,n) if(dfn[i]==0)Tarjan(i); } int main() {while(scanf("%d%d", &n, &m)!=EOF && (n||m)) {Init();FF(i,1,m) {int u, v;scanf("%d%d", &u, &v);Addedge(u, v);}Solve();if(sum==1) puts("Yes");else puts("No");}return 0; } Tarjan求強(qiáng)連通

轉(zhuǎn)載于:https://www.cnblogs.com/sbfhy/p/6349736.html

總結(jié)

以上是生活随笔為你收集整理的HDU-1269 Tarjan求强连通分量，模板题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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