帮别人做网站哪里可以接单/百度seo优化

闲来无事，看到了拓扑排序就学习了一下。

拓扑排序：

  算导上说是使用深搜来对有向无环图进行排序，得到一种线性次序。不过深搜的理解还理解不到。估计是深搜学的不怎么样吧！

  说说我理解的这个线性次序吧。我认为算导上的例子就特别好。早上起来穿衣服的顺序。进过拓扑排序，就能得到一个正确的穿衣次序。

算法执行顺序：
   第一步，找到入度为以的结点，入队。

   第二步，删除与找到的结点相连的边，继续第一步。

   直到所有的结点入队。队列中的一个线性顺序就为一个拓扑排序

现在，以算导上的穿衣例子来实现。

形成环的条件是，入度为0的结点不存在了。

比如，一个结点入队了，剩下的结点也可能成环。

//
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;const int N=10;
int Enter[N];//来记录每个结点的入度.
bool Vis[N];int main()
{
//    freopen("11.txt","r",stdin);int n,m;//n个结点,m条边.vector<int> v[N];//邻接表存图.queue<int> q;int first,than;cin>>n>>m;for(int i=1;i<=m;i++){cin>>first>>than;v[first].push_back(than);Enter[than]++;}while(q.size()<n){int point;for(int i=1;i<=n;i++)if(!Vis[i]&&Enter[i]==0){point=i;Vis[i]=true;break;}printf("pppp%d\n",point);q.push(point);for(int i=0;i<v[point].size();i++)Enter[v[point][i]]--;}while(!q.empty()){printf("%d ",q.front());q.pop();}printf("\n");
}

当然，穿衣的顺序可能有多种，这里，只能跑出来一种，但是，他是正确的。

当然对于，条件比较少的问题，其问题的解可能是不唯一的。

对于拓扑排序来说，最基础的问题结构应该是，比赛排名这一种问题吧。

NYOJ 349&&496就是这类问题。

496链接

这个题意就是，是否存在一种一种唯一顺序。

 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;const int N=30;
bool Map[N][N];
int Enter[N];
char Sorted[N];
int n,m;
char a,b;bool TopSort(){int top=0;while(1){int count=0,p;for(int i=1;i<=n;i++)if(Enter[i]==0){count++;p=i;}if(count!=1)  break;else{Sorted[top++]=p+'A'-1;Enter[p]=-1;for(int i=1;i<=n;i++)if(Map[p][i]){Map[p][i]=false;Enter[i]--;}}}Sorted[top]='\0';if(strlen(Sorted)==n) return true;else return false;
}int main(){int T;cin>>T;while(T--){CLR(Enter,0);CLR(Map,0);cin>>n>>m;for(int i=1;i<=m;i++){cin>>a>>b;Enter[b-'A'+1]++;Map[a-'A'+1][b-'A'+1]=true;}if(TopSort()) printf("%s\n",Sorted);else printf("No Answer\n");}return 0;
}        

用vector实现了一下。

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;const int N=30;
char Sorted[N];
int n,m,Enter[N];
vector<int> v[N];bool TopoSort(){int top=0;while(1){int count=0,p;for(int i=1;i<=n;i++)if(Enter[i]==0){count++;p=i;}if(count!=1) break;else{Enter[p]=-1;Sorted[top++]=p+'A'-1;for(unsigned i=0;i<v[p].size();i++)Enter[v[p][i]]--;}}Sorted[top]='\0';if(strlen(Sorted)==unsigned(n)) return true;else return false;
}
int main()
{int T;scanf("%d",&T);while(T--){char a,b;for(int i=1;i<=N;i++)v[i].clear();CLR(Enter,0);scanf("%d%d",&n,&m);getchar();for(int i=1;i<=m;i++){scanf("%c %c",&a,&b);getchar();v[a-'A'+1].push_back(b-'A'+1);Enter[b-'A'+1]++;}if(TopoSort())printf("%s\n",Sorted);else printf("No Answer\n");}return 0;
}

349题目链接

这个题题目的意思：

也是确定一个排序。

在前几个偏序回得出结论。

结论有，矛盾了，有确定的序列，没有确定的序列但也不矛盾。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;const int N=30;
char Sorted[N];
int n,m;int TopSort(bool map[][N],int enter[]){int top=0;bool mark=false;for(int k=1;k<=n;k++){int count=0,p;for(int i=1;i<=n;i++){if(enter[i]==0){p=i;count++;}}if(count==0) return -1;else if(count>1) {mark=true;}//该题下,因为后续的可能产生矛盾所以，即使找到的序列不唯一//也要先确定一种序列看看是否后续是否后续是否回矛盾.//而,序列不唯一只需要标记一下就可以了.enter[p]=-1;Sorted[top++]=p+'A'-1;for(int i=1;i<=n;i++){if(map[p][i]) enter[i]--;}}Sorted[top]='\0';if(mark) return 0;else return 1;
}int main()
{
//    freopen("11.txt","r",stdin);while(cin>>n>>m&&(n||m)){bool Map[N][N],flag=false;int Enter[N];CLR(Map,0);CLR(Enter,0);getchar();char a,b;for(int k=1;k<=m;k++){scanf("%c<%c",&a,&b);getchar();Map[a-'A'+1][b-'A'+1]=true;Enter[b-'A'+1]++;bool map[N][N];//作为传入值用.int enter[N];CLR(map,0);CLR(enter,0);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)map[i][j]=Map[i][j];enter[i]=Enter[i];}if(!flag){int ans=TopSort(map,enter);if(ans==-1){printf("Inconsistency found after %d relations.\n",k);flag=true;}else if(ans==1){printf("Sorted sequence determined after %d relations: %s.\n",k,Sorted);flag=true;}}}if(!flag) printf("Sorted sequence cannot be determined.\n");}return 0;
}

拓扑排序就到这里了。

总结几点：

第一，拓扑排序，排的是有向无环图。

第二，要深刻理解这个无环。可能有的结点进队后，剩余的结点就成环了，这样也是不能得到一个合理是序列的。

第三，以后要弄个明白这个深搜的思想。