首页 > 代码库 > hello大家好，我是拓扑排序
hello大家好，我是拓扑排序
发几个以前写的拓扑排序，回顾一下。
拓扑排序，一般不会单独考，主要要求还是掌握好这个概念，有个感性的认识，以及能快速的写出求拓扑排序的程序，进而继续接下来对图的处理，或是比如dp之类的算法，又或者是判断有无环之类。求拓扑序主要就是运用队列，push入度为0的点，删掉它们出去的边，重复这个操作。像要是求字典序最小，就可以用优先队列。
TOJ 3993 求字典序最小的拓扑排序
1 #include<cstdio> 2 #include<queue> 3 #include<cstring> 4 using namespace std; 5 6 int ans[110], in[110]; 7 bool e[110][110]; 8 int n, m; 9 int main()10 {11 int T, x, y;12 scanf("%d", &T);13 while(T--)14 {15 memset(e, 0, sizeof(e));16 memset(in, 0, sizeof(in));17 scanf("%d %d", &n, &m);18 for (int i = 0; i < m; i++){19 scanf("%d %d", &x, &y);20 if (!e[x][y]){21 e[x][y] = 1;22 in[y]++;23 }24 }25 priority_queue<int, vector<int>, greater<int> > q;26 for (int i = 1; i <= n; i++)27 if (!in[i]) q.push(i);28 int cnt = 0;29 while(!q.empty()){30 int u = q.top();31 q.pop();32 ans[++cnt] = u;33 for (int i = 1; i <= n; i++)34 if (e[u][i]){35 in[i]--;36 if (!in[i]) q.push(i);37 }38 }39 if (cnt == n){40 for (int i = 1; i <= n; i++)41 printf("%d ", ans[i]);42 printf("\n");43 }44 else printf("Low IQ\n");45 }46 return 0;47 }
POJ 3687 反向建图求拓扑排序
1 #include<cstring> 2 #include<cstdio> 3 #include<queue> 4 using namespace std; 5 6 int ans[210], in[210]; 7 bool e[210][210]; 8 int main() 9 {10 int T, n, m, x, y;11 scanf("%d", &T);12 while(T--)13 {14 memset(e, false, sizeof(e));15 memset(in, 0, sizeof(in));16 scanf("%d %d", &n, &m);17 for (int i = 0; i < m; i++){18 scanf("%d %d", &x, &y);19 if (!e[y][x]){20 e[y][x] = true;21 in[x] ++;22 }23 }24 priority_queue<int> q;25 for (int i = 1; i <= n; i++)26 if (!in[i]) q.push(i);27 int cnt = n;28 while(!q.empty()){29 int u = q.top(); q.pop();30 ans[u] = cnt --;31 for (int i = 1; i <= n; i++)32 if (e[u][i]){33 in[i] --;34 if (!in[i]) q.push(i);35 }36 }37 if (cnt == 0){38 for (int i = 1; i < n; i++)39 printf("%d ", ans[i]);40 printf("%d\n", ans[n]);41 }42 else printf("-1\n");43 }44 return 0;45 }
POJ 1270 按字典序输出所有拓扑排序，这个代码写得比较dirty
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<algorithm> 5 #include<string> 6 #include<iostream> 7 using namespace std; 8 9 char s1[1000], s2[1000];10 string ans[400];11 int n, cnt;12 bool vis[50], e[50][50];13 int in[50], a[50];14 void dfs(int dep, string ss)15 {16 if (dep == n){17 ans[cnt++] = ss;18 return;19 }20 for (int i = 0; i < n; i++)21 if (!in[a[i]] && !vis[a[i]]){22 vis[a[i]] = true;23 char tmp = a[i] + ‘a‘ - 1;24 ss.append(1, tmp);25 for (int j = 0; j < n; j++)26 if (e[a[i]][a[j]]) in[a[j]] --;27 28 dfs(dep+1, ss);29 30 vis[a[i]] = false;31 ss.erase(ss.length()-1, 1);32 for (int j = 0; j < n; j++)33 if (e[a[i]][a[j]]) in[a[j]] ++;34 }35 return;36 }37 bool cmp(string a, string b){38 return a < b;39 }40 int main()41 {42 bool flag = true;43 while(cin.getline(s1, 1000))44 {45 if (flag) flag = false;46 else printf("\n");47 cin.getline(s2, 1000);48 n = 0;49 for (int i = 0; i < strlen(s1); i++){50 if (s1[i] != ‘ ‘){51 a[n++] = s1[i] - ‘a‘ + 1;52 }53 }54 // for (int i = 0; i < n; i++)55 // printf("%d\n", a[i]);56 memset(e, 0, sizeof(e));57 memset(in, 0, sizeof(in));58 memset(vis, false, sizeof(vis));59 int p1 = 0, p2 = 0;60 for (int i = 0; i < strlen(s2); i++){61 if (s2[i] != ‘ ‘){62 if (p1 == 0){63 p1 = s2[i] - ‘a‘ + 1;64 }65 else{66 p2 = s2[i] - ‘a‘ + 1;67 e[p1][p2] = true; 68 in[p2] ++;69 p1 = p2 = 0;70 }71 }72 }73 string ss = "";74 cnt = 0;75 dfs(0, ss);76 sort(ans, ans+cnt, cmp);77 for (int i = 0; i < cnt; i++)78 cout << ans[i] << endl;79 }80 return 0;81 }
HDU 1285 求字典序最小拓扑序
1 #include<cstring> 2 #include<cstdio> 3 #include<queue> 4 using namespace std; 5 6 int en[510], in[510]; 7 int n, m, x, y, esize; 8 struct edge{ 9 int n, v;10 } e[30000];11 void insert(int u, int v)12 {13 esize ++;14 e[esize].v = v;15 e[esize].n = en[u];16 en[u] = esize;17 }18 int main()19 {20 while(scanf("%d %d", &n, &m) != EOF)21 {22 memset(en, -1, sizeof(en));23 memset(in, 0, sizeof(in));24 esize = -1;25 for(int i = 0; i < m; i++){26 scanf("%d %d", &x, &y);27 insert(x, y);28 in[y]++;29 }30 priority_queue<int, vector<int>, greater<int> > q;31 for (int i = 1; i <= n; i++){32 if (!in[i]) q.push(i);33 }34 bool flag = true;35 while(!q.empty()){36 int t = q.top(); q.pop();37 if (flag){38 flag = false;39 printf("%d", t);40 }41 else printf(" %d", t);42 for (int tt = en[t]; tt != -1; tt = e[tt].n){43 int v = e[tt].v;44 in[v]--;45 if (!in[v]) q.push(v);46 }47 }48 printf("\n");49 }50 return 0;51 }
HDU 3231 在三个坐标轴方向上做拓扑排序，对这题还挺有印象，当时wa了好几次卡了很久，记得这题还是某个区预赛的题。不知道真到比赛，会是什么样。我能很快的做出来吗？
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 using namespace std; 5 6 struct edge{ 7 int n, v; 8 } e[3][603000]; 9 int ans[3000][3], en[3][3000], in[3][3000];10 int n, r, esize[3];11 void insert(int t, int u, int v)12 {13 e[t][esize[t]].v = v;14 e[t][esize[t]].n = en[t][u];15 en[t][u] = esize[t];16 esize[t] ++;17 in[t][v]++;18 }19 int main()20 {21 int x, y, ca = 0;22 char ch[10];23 while(scanf("%d %d", &n, &r) && (n + r))24 {25 ca ++;26 memset(in, 0, sizeof(in));27 memset(en, -1, sizeof(en));28 memset(esize, 0, sizeof(esize));29 for (int i = 1; i <= n; i++){30 insert(0, i, i+n);31 insert(1, i, i+n);32 insert(2, i, i+n);33 }34 for (int i = 0; i < r; i++){35 //getchar();36 scanf("%s %d %d", ch, &x, &y);37 if (ch[0] == ‘I‘){38 insert(0, x, y+n);39 insert(1, x, y+n);40 insert(2, x, y+n);41 insert(0, y, x+n);42 insert(1, y, x+n);43 insert(2, y, x+n);44 }45 else if (ch[0] == ‘X‘){46 insert(0, x+n, y);47 }48 else if (ch[0] == ‘Y‘){49 insert(1, x+n, y);50 }51 else if (ch[0] == ‘Z‘)52 insert(2, x+n, y);53 }54 bool findans = true;55 for (int t = 0; t < 3; t++){56 queue<int> q;57 for (int i = 1; i <= n * 2; i++){58 if (in[t][i] == 0) {//printf("t:%d %d\n", t, i);59 q.push(i);60 }61 }62 int u, v, p;63 int cnt = 0;64 while(!q.empty()){65 int u = q.front(); q.pop();66 ans[u][t] = ++cnt;67 for (p = en[t][u]; p != -1; p = e[t][p].n){68 v = e[t][p].v;69 in[t][v] --;70 if (!in[t][v]){//printf("t:%d %d\n", t, v);71 q.push(v);72 }73 }74 }75 //printf("%d\n", cnt);76 if (cnt != (n*2)) {findans = false; break;}77 }78 if (findans){79 printf("Case %d: POSSIBLE\n", ca);80 for (int i = 1; i <= n; i++)81 printf("%d %d %d %d %d %d\n", ans[i][0], ans[i][1], ans[i][2], 82 ans[i+n][0], ans[i+n][1], ans[i+n][2]);83 }84 else85 printf("Case %d: IMPOSSIBLE\n", ca);86 if (ca >= 1) printf("\n");87 }88 return 0;89 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。