拓?fù)渑判虻膶?shí)現(xiàn)條件，以及結(jié)合應(yīng)用場(chǎng)景，我們都能得到拓?fù)渑判蜻m用于DAG圖（Directed Acyclic Graph簡(jiǎn)稱DAG）有向無(wú)環(huán)圖，?根據(jù)關(guān)系我們能得到一個(gè)線性序列，實(shí)現(xiàn)的方式是DFS，具體的實(shí)現(xiàn)原理，我們將在下一篇博客中講解。

#include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; const int maxn=100+10; int n,m; vector<int> G[maxn];//G[i]表示i節(jié)點(diǎn)所指向的所有其他點(diǎn) int in[maxn];//節(jié)點(diǎn)入度 bool topo()//判斷該圖是否可拓?fù)渑判?{queue<int> Q;int sum=0;//記錄可拆解的點(diǎn)數(shù)目for(int i=0;i<n;i++)if(in[i]==0)Q.push(i);while(!Q.empty()){int u=Q.front(); Q.pop();sum++;for(int i=0;i<G[u].size();i++){int v=G[u][i];if(--in[v]==0) Q.push(v);}}return sum==n;//可完全拓?fù)?} int main() {while(scanf("%d%d",&n,&m)==2&&n){memset(in,0,sizeof(in));for(int i=0;i<n;i++) G[i].clear();for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);in[v]++;}printf("%s\n",topo()?"YES":"NO");}return 0; }

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的图论--拓扑排序--判断一个图能否被拓扑排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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