?

一、什么是拓撲排序
在圖論中，拓撲排序（Topological Sorting）是一個有向無環圖（DAG, Directed Acyclic Graph）的所有頂點的線性序列。且該序列必須滿足下面兩個條件：

每個頂點出現且只出現一次。若存在一條從頂點 A 到頂點 B 的路徑，那么在序列中頂點 A 出現在頂點 B 的前面。有向無環圖（DAG）才有拓撲排序，非DAG圖沒有拓撲排序一說。

例如，下面這個圖：
它是一個 DAG 圖，那么如何寫出它的拓撲排序呢？這里說一種比較常用的方法：

從 DAG 圖中選擇一個 沒有前驅（即入度為0）的頂點并輸出。
從圖中刪除該頂點和所有以它為起點的有向邊。
重復 1 和 2 直到當前的 DAG 圖為空或當前圖中不存在無前驅的頂點為止。后一種情況說明有向圖中必然存在環。

?
于是，得到拓撲排序后的結果是 { 1, 2, 4, 3, 5 }。

通常，一個有向無環圖可以有一個或多個拓撲排序序列。

T題代碼：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
typedef long long ll;
using namespace std;
const int maxn=505;
int n,m,f[maxn],g[maxn];
vector<int>v[maxn];
void topo()
{int k=0,u;for(int i=1;i<=n;i++){u=1;while(f[u]!=0)u++;g[i]=u;f[u]=-1;for(int j=0;j<v[u].size();j++)f[v[u][j]]--;}for(int i=1;i<=n;i++){if(i==n)printf("%d\n",g[i]);elseprintf("%d ",g[i]);}}
int main()
{int x,y;while(cin>>n>>m){for(int i=1;i<=n;i++)v[i].clear();memset(f,0,sizeof(f));while(m--){scanf("%d %d",&x,&y);f[y]++;v[x].push_back(y);}topo();}return 0;
}

優先隊列優化：

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
typedef long long ll;
const int inff=0x3f3f3f3f;
const double eqs=1e-9;
const double E=2.718281828459;
const double pi=acos(-1.0);
using namespace std;
const int maxn=505;
int in[maxn],ans[maxn];
vector<int>v[maxn];
int n,m;
void topo()
{priority_queue<int,vector<int>,greater<int>> q;for(int i=1;i<=n;i++) if(in[i]==0) q.push(i); //入度為0的點int cnt=0;while(!q.empty()){int u=q.top();q.pop();ans[++cnt]=u;for(int i=0;i<v[u].size();i++)//將與u連接的入度減-1{int e=v[u][i];in[e]--;if(in[e]==0) q.push(e);}}
}
int main()
{int x,y;while(cin>>n>>m){for(int i=0;i<=n;i++)v[i].clear(),in[i]=0;for(int i=1;i<=m;i++){cin>>x>>y;in[y]++;//記錄入度v[x].push_back(y);//連邊}topo();for(int i=1;i<=n;i++)printf("%d%c",ans[i],(i==n)?'\n':' ');}}

并查集：

并查集主要用來解決判斷兩個元素是否同屬一個集合，以及把兩個集合合并成一個集合的問題。

題目在下邊的鏈接

http://acm.hdu.edu.cn/showproblem.php?pid=1232

代碼：

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
typedef long long ll;
const int inff=0x3f3f3f3f;
const double eqs=1e-9;
const double E=2.718281828459;
const double pi=acos(-1.0);
using namespace std;
const int maxn=1005;
int f[maxn];
int find1(int x)
{while(x!=f[x])x=f[x];return x;
}
int find(int x)
{if(x==f[x]) return x;else return f[x]=find(f[x]);
}
void unionn(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy)f[fx]=fy;
}
int main()
{int n,m,x,y;while(cin>>n,n){cin>>m;for(int i=1;i<=n;i++) f[i]=i;for(int i=1;i<=m;i++){scanf("%d %d",&x,&y);unionn(x,y);}int ans=0;for(int i=1;i<=n;i++)if(find(i)==i) ans++;cout<<ans-1<<endl;}
}

?

總結

以上是生活随笔為你收集整理的拓扑排序和并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

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