拓扑排序
拓扑排序是将一个DAG图的所有顶点排成一个线性序列，使得图中任意一对顶点（u，v）
若存在边，则u在线性排列中出现在v之前的排列方式
(1)算法描述：
(a)从网中选择一个入度为零的顶点输出；
(b)删除该顶点及其于该点有关的所有边；
(c)是否还有入度为零的顶点？若有，执行(a)，否则结束。
用邻接矩阵时间复杂度为O(N*N)，邻接表的时间复杂度为O(E)
http://acm.hdu.edu.cn/showproblem.php?pid=1285
即输出字典序最小的拓扑排序
1 #include <stdio.h> 2 #include <string.h> 3 #include <stack> 4 #include <algorithm> 5 using namespace std; 6 const int N = 555; 7 int g[N][N]; 8 int ans[N],in[N]; 9 void topSort(int n, int m) 10 { 11 int i,j,k; 12 for(i=1; i<=n; ++i) 13 for(j=1; j<=n; ++j) 14 if(g[i][j]) 15 in[j]++;//计算每个点的入度 16 for(i=1; i<=n; ++i) 17 { 18 for(j=1; in[j]&&j<=n; ++j)//找到入度为0的点 19 NULL; 20 in[j] = -1; 21 ans[i]=j;//记录 22 for(k=1; k<=n; ++k) 23 if(g[j][k])//删边 24 in[k]--; 25 } 26 } 27 int main() 28 { 29 int n,m,i,u,v; 30 while(scanf("%d%d",&n,&m)!=EOF) 31 { 32 memset(g,0,sizeof(g)); 33 memset(in,0,sizeof(in)); 34 for(i=0; i<m; ++i) 35 { 36 scanf("%d%d",&u,&v); 37 g[u][v] = 1; 38 } 39 topSort(n,m); 40 for(i=1; i<=n; ++i) 41 { 42 if(i==1) 43 printf("%d",ans[i]); 44 else 45 printf(" %d",ans[i]); 46 } 47 puts(""); 48 } 49 return 0; 50 }
View Code
http://acm.hdu.edu.cn/showproblem.php?pid=2647
给定n个人，m条边
边u->v表示 u的工资要比v高， 每个人的基础工资为888，问总共的工资最少是多少。
可以看做是这么一种情况，把整个图分为若干层，层内的工资相等，层与层之间的工资相差1.
u->v表示u的工资比v高，那么要先确定v才能确定u，那么可以反向建图。
1 #include <stdio.h> 2 #include <string.h> 3 #include <vector> 4 #include <stack> 5 using namespace std; 6 const int N = 10000 + 10; 7 vector<int> g[N]; 8 stack<int> st; 9 int in[N],add[N],cnt; 10 inline int max(const int &a, const int &b) 11 { 12 return a < b ? b : a; 13 } 14 void topSort(int n, int m) 15 { 16 int u,i; 17 for(i=1; i<=n; ++i) 18 if(in[i]==0) 19 st.push(i); 20 while(!st.empty()) 21 { 22 u = st.top();//u出栈，表示u的工资已经确定，那么可以推出u指向的顶点的工资 23 cnt++; 24 st.pop(); 25 for(i=0; i<g[u].size(); ++i) 26 { 27 --in[g[u][i]]; 28 if(in[g[u][i]]==0) 29 st.push(g[u][i]); 30 add[g[u][i]] = max(add[u]+1,add[g[u][i]]);//如果当前的值比前驱加上一的值还小就要更新当前点的值 31 32 } 33 } 34 } 35 void init(int n) 36 { 37 cnt = 0; 38 for(int i=1; i<=n; ++i) 39 { 40 g[i].clear(); 41 add[i] = in[i] = 0; 42 } 43 } 44 int main() 45 { 46 int n,m,i,u,v; 47 while(scanf("%d%d",&n,&m)!=EOF) 48 { 49 init(n); 50 for(i=0; i<m; ++i) 51 { 52 scanf("%d%d",&u,&v); 53 g[v].push_back(u);//反向建图 54 in[u]++; 55 } 56 topSort(n,m); 57 int ans = 0; 58 if(cnt==n) 59 { 60 for(i=1; i<=n; ++i) 61 ans += add[i] + 888; 62 printf("%d\n",ans); 63 } 64 else 65 printf("-1\n"); 66 } 67 }
View Code
http://acm.hdu.edu.cn/showproblem.php?pid=2647
给定n个人，m条边
判断图是不是DAG图。 拓扑排序O(E)， bellman O(VE) ， 使用邻接表的dfs O(V+E) ，floyd O(N*N*N)
其余代码见 http://www.cnblogs.com/justPassBy/p/4342599.html
1 #include <stdio.h> 2 #include <string.h> 3 #include <vector> 4 #include <stack> 5 using namespace std; 6 const int N = 10000 + 10; 7 vector<int> g[N]; 8 stack<int> st; 9 int in[N],add[N],cnt; 10 inline int max(const int &a, const int &b) 11 { 12 return a < b ? b : a; 13 } 14 void topSort(int n, int m) 15 { 16 int u,i; 17 for(i=1; i<=n; ++i) 18 if(in[i]==0) 19 st.push(i); 20 while(!st.empty()) 21 { 22 u = st.top(); 23 cnt++; 24 st.pop(); 25 for(i=0; i<g[u].size(); ++i) 26 { 27 --in[g[u][i]]; 28 if(in[g[u][i]]==0) 29 st.push(g[u][i]); 30 31 32 } 33 } 34 } 35 void init(int n) 36 { 37 cnt = 0; 38 for(int i=1; i<=n; ++i) 39 { 40 g[i].clear(); 41 add[i] = in[i] = 0; 42 } 43 } 44 int main() 45 { 46 int n,m,i,u,v; 47 while(scanf("%d%d",&n,&m)!=EOF) 48 { 49 if(n==0 && m==0) 50 break; 51 init(n); 52 for(i=0; i<m; ++i) 53 { 54 scanf("%d%d",&u,&v); 55 u++; 56 v++; 57 g[u].push_back(v); 58 in[v]++; 59 } 60 topSort(n,m); 61 if(cnt==n)//能生成n个顶点的序列，说明是DAG图 62 { 63 puts("YES"); 64 } 65 else 66 puts("NO"); 67 } 68 }
View Code
http://acm.hdu.edu.cn/showproblem.php?pid=1811
根据所给的信息判定能否确定唯一排名。
题目的难点在于=号的处理。 我们可以利用并查集将相等的结点并在一个集合里。然后再使用拓扑排序就可以了。
1、如果每次入栈的结点大于1个，那么拓扑排序不唯一。 这很好理解
2、如果出栈的顶点个数小于总顶点个数，那么存在回路。
1 #include <stdio.h> 2 #include <string.h> 3 #include <vector> 4 #include <stack> 5 using namespace std; 6 const int N = 10000 + 10; 7 int u[N],v[N]; 8 int in[N],father[N]; 9 char str[N][2]; 10 vector<int> g[N]; 11 stack<int> st; 12 int ans,cnt; 13 void init(int n) 14 { 15 ans = cnt = 0; 16 for(int i=0; i<=n; ++i) 17 { 18 in[i] = 0; 19 father[i] = i; 20 g[i].clear(); 21 } 22 } 23 int topSort(int n, int m) 24 { 25 int i,tmp = 0,flag = 0,k = 0; 26 for(i=0; i<n; ++i) 27 if(father[i]==i) 28 { 29 cnt++; 30 if(in[i]==0) 31 { 32 st.push(i); 33 tmp++; 34 } 35 if(tmp>1)//如果一次入栈的结点大于1个，那么就说明拓扑排序不唯一 36 flag = 2; 37 } 38 while(!st.empty()) 39 { 40 int u = st.top(); 41 st.pop(); 42 k++; 43 tmp = 0; 44 for(i=0; i<g[u].size(); ++i) 45 { 46 int v = g[u][i]; 47 in[v]--; 48 if(in[v]==0) 49 { 50 tmp++; 51 st.push(v); 52 } 53 } 54 if(tmp>1) flag = 2; 55 } 56 if(k < cnt) flag = 1;//存在回路 57 return flag; 58 } 59 int find(int x) 60 { 61 if(x == father[x]) 62 return x; 63 return father[x] = find(father[x]); 64 } 65 int main() 66 { 67 int n,m,i,ru,rv; 68 while(scanf("%d%d",&n,&m)!=EOF) 69 { 70 init(n); 71 for(i=0; i<m; ++i) 72 { 73 scanf("%d%s%d",&u[i],str[i],&v[i]); 74 if(str[i][0]==\'=\')//将相等的结点并在一个集合里 75 { 76 ru = find(u[i]); 77 rv = find(v[i]); 78 if(ru!=rv) 79 father[ru] = rv; 80 } 81 } 82 for(i=0; i<n; ++i) find(i);//这样就能用father[i]得到i的父亲 83 for(i=0; i<m; ++i) 84 { 85 if(father[u[i]] == father[v[i]] && str[i][0]!=\'=\') 86 { 87 ans = 1; 88 break; 89 } 90 else if(str[i][0]==\'>\') 91 { 92 g[father[u[i]]].push_back(father[v[i]]); 93 in[father[v[i]]]++; 94 } 95 else if(str[i][0]==\'<\') 96 { 97 g[father[v[i]]].push_back(father[u[i]]); 98 in[father[u[i]]]++; 99 } 100 } 101 if(!ans) ans = topSort(n,m); 102 if(!ans) puts("OK"); 103 else if(ans==1) puts("CONFLICT"); 104 else puts("UNCERTAIN"); 105 } 106 return 0; 107 }
View Code
http://poj.org/problem?id=1094
给定n个点，m条边，
要我们逐步判断随着边的增加，能否确定唯一拓扑排序，或者是否有环。 否则就是不能确定
先判断有没有环，如果有环，输出有环
如果没有环，那么拓扑判断是否能确定唯一排序
1 #include <stdio.h> 2 #include <string.h> 3 #include <vector> 4 using namespace std; 5 const int N = 30; 6 int g[N][N],start,n,m,in[N],ans[N]; 7 bool vis[N],vis2[N],hasCircle,confirmSequeue; 8 void dfs(int u) 9 { 10 for(int i=0; i<n; ++i) 11 { 12 if(g[u][i]==1) 13 { 14 if(start==i) 15 { 16 hasCircle = true; 17 return; 18 } 19 if(!vis2[i]) 20 { 21 vis2[i] = true; 22 dfs(i); 23 } 24 25 } 26 } 27 } 28 void topSort() 29 { 30 int i,j,k; 31 for(i=0; i<n; ++i) 32 for(j=0; j<n; ++j) 33 if(g[i][j]) 34 in[j]++; 35 int cnt = 0; 36 for(j=0; j<n; ++j) 37 if(in[j]==0) 38 cnt++; 39 if(cnt>1)//不能确定唯一拓扑排序 40 { 41 confirmSequeue = false; 42 return; 43 } 44 for(i=0; i<n; ++i) 45 { 46 for(j=0;in[j]&&j<n;++j) 47 NULL; 48 in[j] = -1; 49 ans[i] = j; 50 cnt = 0; 51 for(k=0; k<n; ++k) 52 { 53 if(g[j][k]) 54 { 55 in[k]--; 56 if(in[k]==0) 57 cnt++; 58 } 59 if(cnt>1) 60 { 61 confirmSequeue = false; 62 return; 63 } 64 } 65 } 66 } 67 int main() 68 { 69 int i,cnt,u,v,j; 70 char str[5]; 71 while(true) 72 { 73 scanf("%d%d",&n,&m); 74 if(n==0 && m==0) break; 75 memset(vis,0,sizeof(vis)); 76 memset(g,0,sizeof(g)); 77 hasCircle = false; 78 confirmSequeue = true; 79 cnt = 0; 80 for(i=0; i<m; ++i) 81 { 82 scanf("%s",str); 83 u = str[0] - \'A\'; 84 v = str[2] - \'A\'; 85 g[u][v] = 1; 86 if(!vis[u]) {vis[u] = true; cnt++;} 87 if(!vis[v]) {vis[v] = true; cnt++;} 88 for(j=0; j<n; ++j)//dfs判断是否有环 89 { 90 memset(vis2,0,sizeof(vis2)); 91 vis2[j] = true; 92 start = j; 93 dfs(j); 94 if(hasCircle) break; 95 } 96 if(hasCircle) break; 97 if(cnt==n)//有n个顶点的时候才进行拓扑排序 98 { 99 confirmSequeue = true; 100 memset(in,0,sizeof(in)); 101 topSort(); 102 if(confirmSequeue) 103 break; 104 } 105 } 106 if(cnt == n && confirmSequeue) 107 { 108 printf("Sorted sequence determined after %d relations: ",i+1); 109 for(j=0; j<n; ++j) 110 printf("%c",ans[j]+\'A\'); 111 puts("."); 112 } 113 else if(hasCircle) 114 printf("Inconsistency found after %d relations.\n",i+1); 115 else 116 printf("Sorted sequence cannot be determined.\n"); 117 for(i++;i<m; ++i) 118 scanf("%s",str); 119 } 120 }
View Code
版权声明：本文为justPassBy原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。