首页 > 代码库 > CERC 2012 J (拓扑排序)
CERC 2012 J (拓扑排序)
题意:一些具有拓扑序的节点需要染色,这些节点一共分为两类。问你按照给出的拓扑顺序染色完结点最少需要多少次切换。
思路:我们按照拓扑排序的做法,建立两个栈分别存放两种不同种类的节点,每次把一个栈中的所有节点都处理完了才处理另一个,这样切换次数即为最终答案。
代码如下:
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-06-30 12:30 5 * Filename : cerc_j.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 100000+10; 34 int n, m, vex[LEN], ind[LEN], tmp_ind[LEN]; 35 bool vis[LEN]; 36 struct E{ 37 int to, next; 38 }edge[LEN*10]; 39 int head[LEN], top; 40 41 void init(){ 42 top = 0; 43 memset(head, -1, sizeof head); 44 } 45 46 void addedge(int u, int v){ 47 edge[top].next = head[u]; 48 edge[top].to = v; 49 head[u] = top++; 50 } 51 52 int solve(int flag){ 53 for(int i=0; i<n; i++) 54 ind[i] = tmp_ind[i]; 55 memset(vis, 0, sizeof vis); 56 queue<int> q1, q0; 57 for(int i=0; i<n; i++){ 58 if(!ind[i]){ 59 vis[i] = 1; 60 if(!vex[i]) q0.push(i); 61 else q1.push(i); 62 } 63 } 64 int ret = 0, cnt = 0; 65 for(;;ret++){ 66 if(flag){ 67 if(q1.empty()) { 68 ret--; break; 69 } 70 while(!q1.empty()){ 71 int nv = q1.front(); q1.pop(); 72 cnt ++; 73 for(int i=head[nv]; i!=-1; i=edge[i].next){ 74 int nx = edge[i].to; 75 ind[nx] --; 76 if(!ind[nx] && !vis[nx]){ 77 vis[nx] = 1; 78 if(vex[nx]) q1.push(nx); 79 else q0.push(nx); 80 } 81 } 82 } 83 }else{ 84 if(q0.empty()) { 85 ret--; break; 86 } 87 while(!q0.empty()){ 88 int nv = q0.front(); q0.pop(); 89 cnt ++; 90 for(int i=head[nv]; i!=-1; i=edge[i].next){ 91 int nx = edge[i].to; 92 ind[nx] --; 93 if(!ind[nx] && !vis[nx]){ 94 vis[nx] = 1; 95 if(vex[nx]) q1.push(nx); 96 else q0.push(nx); 97 } 98 } 99 }100 }101 flag = !flag;102 }103 if(cnt != n) return INF;104 return ret;105 }106 107 int main()108 {109 // freopen("in.txt", "r", stdin);110 111 int a, b, T;112 scanf("%d", &T);113 while(T--){114 init();115 memset(tmp_ind, 0, sizeof tmp_ind);116 scanf("%d%d", &n, &m);117 for(int i=0; i<n; i++){118 scanf("%d", &vex[i]);119 vex[i] --;120 }121 for(int i=0; i<m; i++){122 scanf("%d%d", &a, &b);123 a--, b--;124 addedge(a, b);125 tmp_ind[b] ++;126 }127 int ans = min(solve(0), solve(1));128 printf("%d\n", ans);129 }130 return 0;131 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。