心得：Topsort不仅用于job／work的排序，字典序的排序，还可以适用于任意具有偏序关系的问题，

只要可以把问题转换为有向无环图，然后知晓其偏序，之后就是表示边／入度，然后用拓扑排序的思想去计算。

注意拓扑排序的唯一性是在全序关系的条件下建立起来的

注意拓扑排序是针对有向五环图。

欧拉回路和哈密顿路径：

哈密顿路径：经过所有的顶点正好访问一次的路径。

 

Knhn算法的实现：考虑入度为0的点

DFS算法的实现：考虑出度为0的点

 

uva,200

一开始没看懂，后来知道了，是给你几行索引是按照一种语言的字典序排序的

例如: xwy zx  z>x   zxy zxw  w>y  zxw ywwx  y>z   最后字母的大小顺序  x<z<y<w

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6  7 vector
          
            ans; 8 vector
           
             toPoint[100]; 9 int visit[100] = { 0};10 int deg[100] = { 0}; // deg[i]=1:沒有被其他點連入 deg[i]=2:被其他點連入11 void DFS(char n);12 13 int main()14 {15 // freopen("input.txt","rt",stdin);16 ios::sync_with_stdio(false);17 string a, b;18 cin >> a;19 while (cin >> b && b != "#") {20 int L = (a.size() > b.size()) ? b.size() : a.size();21 for (int i = 0; i < L; ++i) {22 if (deg[a[i]] == 0) deg[a[i]] = 1;23 if (deg[b[i]] == 0) deg[b[i]] = 1;24 if (b[i] != a[i]) {25 toPoint[a[i]].push_back(b[i]);26 deg[b[i]] = 2;27 break;28 }29 }30 a = b;31 }32 for (char i = 'A'; i <= 'Z'; ++i)33 if (deg[i] == 1)34 DFS(i);35 36 for (auto iter = ans.rbegin(); iter != ans.rend(); ++iter)37 cout << *iter;38 cout << endl;39 }40 void DFS(char n)41 {42 if (visit[n] == 1) return;43 visit[n] = 1;44 45 for (char nxt : toPoint[n])46 if (visit[nxt] != 2)47 DFS(nxt);48 visit[n] = 2;49 ans.push_back(n);50 }
           
          
         
        
       
      

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 using namespace std; 6  7 char list[10001][100]; 8 int map[27][27]; 9 int used[27];10 int stack[27];11 int stack_size=0;12 13 void dfs(int s)14 {15     used[s]=0;16     for(int i=0;i<27;++i)17         if(used[i] && map[s][i])18             dfs(i);19     stack[stack_size++]=s+'A';20 }21 22 int main()23 {24     int count=0;25     while(scanf("%s",list[count]) && list[count][0]!='#')26         count++;27     memset(used,0,sizeof(used));28     memset(map,0,sizeof(map));29     used[list[0][0]-'A']=1;30     31     for(int i=1;i
        
       
      

uva,10305

dfs搞一搞就可以了

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 using namespace std; 6 const int maxn=105; 7  8 int map[maxn][maxn]; 9 int visit[maxn];10 int stack[maxn];11 int stack_size;12 int n,m;13 14 void dfs(int s)15 {16     visit[s]=1;17     for(int i=1;i<=n;i++)18         if(map[s][i] && !visit[i])19             dfs(i);20     stack[--stack_size]=s;21 }22 23 int main()24 {25     while(scanf("%d%d",&n,&m) && m+n)26     {27         memset(map,0,sizeof(map));28         int a,b;29         for(int i=0;i
        
       
      

 uva,124

参考了大神的代码，第一次接触拓扑排序，我还只停留在一维的思想上，只会打印一组拓扑排序结果，

用dfs把每种可能的结果都搜一下，然后加上限制条件，如果满足len=n则输出。。。。。真的妙！！！豁然开朗

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 8 using namespace std; 9 const int maxn=200;10 11 char ch1[maxn],ch2[maxn],ch3[maxn];12 int n,m,a[maxn],edge[maxn][maxn],to[maxn],vis[maxn],zm[maxn];13 14 bool cmp(char a,char b)15 {16 return a
           
          
         
        
       
      

对next_permutation函数求出所以的排列，然后限制条件，最后输出。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 8 using namespace std; 9 const int maxn=200;10 11 char ch1[maxn],ch2[maxn],ch3[maxn];12 int n,edge[maxn][maxn],to[maxn],vis[maxn],a[maxn],zm[maxn];13 14 15 bool cmp(char a,char b)16 {17 return a
            
             0;i--)23 for(int j=i-1;j>=0;j--)24 if(edge[zm[ch[i]-'a']][zm[ch[j]-'a']]==1)25 return 0;26 return 1;27 }28 29 int main()30 {31 int i,pd=0;32 while(gets(ch1))33 {34 if(!pd)35 pd=1;36 else37 printf("\n");38 gets(ch2);39 for(i=0,n=0;ch1[i];i++)40 {41 if(ch1[i]==' ')42 continue;43 ch3[n++]=ch1[i];44 }45 ch3[n]='\0';46 sort(ch3,ch3+n,cmp);47 memset(edge,-1,sizeof(edge));48 memset(vis,0,sizeof(vis));49 memset(to,0,sizeof(to));50 memset(zm,-1,sizeof(zm));51 52 53 for(i=0;i
            
           
          
         
        
       
      

uva,196

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 using namespace std; 10 const int maxn=2000005; // 开到百万即可 11 int row,col; // 行，列 12 int val[maxn]; // 数值 13 int GetId(int x,int y){ return (x-1)*col+y; } // 得到某个位置的id 14 string S[maxn]; 15 vector
              
                G[maxn]; // 用动态数组建立临接表，我比较喜欢用这种方式 16 int indeg[maxn]; // 入度 17 int Get(const string& str) // 如果格子中是数值，则调用这个函数 18 { 19 int ret=0; 20 for(int i=0;i
               
                ='0'&&str[i]<='9') break; // 找到字母和数字的分界位置 29 } 30 int R=0,C=0; 31 for(int j=0;j
                

que; 57 void toposort() 58 { 59 while(!que.empty()) que.pop(); 60 for(int i=1;i<=row*col;i++) if(!indeg[i]) que.push(i); //入度为0 的加入队列 61 while(!que.empty()) 62 { 63 int now=que.front(); que.pop(); 64 for(int i=0;i

>S[id];101 Get_Val(S[id],id); // 处理102 }103 }104 toposort(); // 拓扑排序105 ans_print(); // 打印106 }107 return 0;108 }