首页 > 代码库 > hdu--1811--并查集&&拓扑排序<好题>
hdu--1811--并查集&&拓扑排序<好题>
做了这题 绝逼 累啊..
mle -- re<stack overflow>--tle--wa---ac
经过这么5步 终于AC了
这题 我觉得可以让你更好地来 理解 拓扑排序的一些细节问题
首先 这题 为什么要用到并查集呢? 因为 会有 A = B这种情况的出现 然后可能再来个 B =C A = D....那么我们就需要将它们全部表示成一个点 那么就是都用一个根结点来表示
然后 这边 是要判断 能不能根据给出的条件 形成一个排列 那么就是个 拓扑问题 根据 > <情况来判断
我觉得 解这题的几点核心思想：
1.如果要对N个元素进行拓扑排序 那么如果每次 入度为0的点超过2个 就会形成多种排序结果 所以 这也就是 一般我们做拓扑的时候 题目会要求我们什么按照字典序来输出什么的 因为存在满足要求情况不止一种啊 但这边 很特殊 它一定严格按照><=来输出 所以我们可以对每次队列中的元素个数进行判断 如果大于一个 就可以确定这是不确定 即 q.size()>1
2.拓扑排序是基于---DAG<有向无环图> 其实也就是告诉我们 可以根据拓扑来判断 这个图中是否存在环? 我们只要每次有一个元素被取出 就进行统计 最后再判断下 一共被取出的元素数目 与 需要进行拓扑的元素数目 是否相等 如果不相等 就可以说它是 成环的
---我感觉 这2点 应该算是最重要的 但还有很多细节 地方要注意的 我一共写了好多份代码...
一开始 我走错了个方向 我忘记考虑了 成环的存在 我判断 A>B 是否与 A<B 同时存在 来判断conflict 这样虽然样例过了但是 我mle同时 也是错误的
恩 对了 这边进行初始入队的时候很重要一点是 这个结点 不仅仅要求是入度为0 而且是 根结点 因为不是根结点的 已经被我们合并掉了 没有纳入我们总的元素数量考虑
所以 这边 我后来做的时候 又犯了一次错误
我们对于输入的 A OP B 需要进行2次处理 第一次是把 = 号关系的2个结点合并 每次 合并 都需要对总的数目--
其实 这个合并不难理解 因为主要是来因对 A = B B = D D>C 这种类似的情况的
touch me
这边 题目是没有要求我们输出最终结果 但是 如果要输出的话 我们也只要根据这句话就好了 ---如果两个人具有相同的Rating，那就按这几个人的RP从高到低来排----
好了 贴下代码 有点乱啊 被这vs搞的
1 #include <iostream> 2 #include <cstring> 3 #include <map> 4 #include <queue> 5 using namespace std; 6 7 bool ans; 8 int n; 9 const int size = 10010; 10 int in[size]; 11 int father[size]; 12 char mp[size][size]; 13 map<char, int>op; 14 queue<int>q; 15 16 int find(int x) 17 { 18 while( father[x]!=-1 ) 19 { 20 father[x] = father[ father[x] ]; 21 x = father[x]; 22 } 23 return x; 24 } 25 26 void topo() 27 { 28 for (int i = n - 1; i >= 0; i--) 29 { 30 if (!in[i]) 31 { 32 q.push(i); 33 } 34 } 35 while (!q.empty()) 36 { 37 if (q.size()>1) 38 ans = true;// uncertain 39 int now = q.front(); 40 q.pop(); 41 for ( int i = 0 ; i<n ; i++ ) 42 { 43 if( mp[now][i]==‘2‘ ) 44 { 45 in[i] --; 46 if( in[i]==0 ) 47 { 48 q.push(i); 49 } 50 } 51 } 52 } 53 } 54 55 int main() 56 { 57 cin.sync_with_stdio(false); 58 int m , x , y; 59 char ch; 60 bool flag; 61 while (cin >> n >> m) 62 { 63 memset(father, -1, n*sizeof(int)); 64 memset(mp,‘0‘, sizeof(mp)); 65 memset(in, 0, n*sizeof(int)); 66 op[‘=‘] = ‘1‘; 67 op[‘>‘] = ‘2‘; 68 op[‘<‘] = ‘3‘; 69 ans = flag = false; 70 while (m--) 71 { 72 cin >> x >> ch >> y; 73 x = find(x); 74 y = find(y); 75 if (mp[x][y]==‘0‘) 76 { 77 if (ch == ‘=‘) 78 { 79 mp[x][y] = ‘1‘;//1是平局 80 mp[y][x] = ‘1‘; 81 father[y] = x; 82 } 83 else if (ch == ‘>‘) 84 { 85 mp[x][y] = ‘2‘;//2是大于 86 mp[y][x] = ‘3‘;//3是小于 87 in[y] ++; 88 } 89 else 90 { 91 mp[x][y] = ‘3‘; 92 mp[y][x] = ‘2‘; 93 in[x] ++; 94 } 95 } 96 else 97 { 98 if (op[ch] != mp[x][y]) 99 {100 flag = true;//conflict101 }102 }103 }104 topo();105 if (flag)106 cout << "CONFLICT" << endl;107 else108 {109 if (ans)110 cout << "UNCERTAIN" << endl;111 else112 cout << "OK" << endl;113 }114 }115 return 0;116 }
1 #include <iostream> 2 #include <cstring> 3 #include <vector> 4 #include <queue> 5 using namespace std; 6 7 int n , cnt; 8 bool CONFLICT , UNCERTAIN; 9 const int size = 10010; 10 int x[size]; 11 int y[size]; 12 char ch[size]; 13 int in[size]; 14 int father[size]; 15 vector<int>ve[size]; 16 queue<int>q; 17 18 void init( ) 19 { 20 memset( father , -1 , sizeof(father) ); 21 memset( in , 0 , sizeof(in) ); 22 for( int i = 0 ; i<size ; i++ ) 23 { 24 ve[i].clear(); 25 } 26 } 27 28 int find( int x ) 29 { 30 return father[x] == -1 ? x : father[x] = find( father[x] ); 31 } 32 33 void topo( ) 34 { 35 for( int i = 0 ; i<n ; i++ ) 36 { 37 if( !in[i] && father[i] == -1 ) 38 { 39 q.push(i); 40 } 41 } 42 while( !q.empty() ) 43 { 44 if( q.size()>1 ) 45 UNCERTAIN = true; 46 int now = q.front(); 47 q.pop(); 48 cnt --; 49 for( int i = 0 ; i<ve[now].size() ; i++ ) 50 { 51 int u = ve[now][i]; 52 if( --in[u] == 0 ) 53 { 54 q.push(u); 55 } 56 } 57 } 58 if( cnt>0 ) 59 CONFLICT = true; 60 } 61 62 int main() 63 { 64 int m , xx , yy; 65 while( cin >> n >> m ) 66 { 67 init( ); 68 cnt = n; 69 CONFLICT = UNCERTAIN = false; 70 for( int i = 0 ; i<m ; i++ ) 71 { 72 cin >> x[i] >> ch[i] >> y[i]; 73 if( ch[i]==‘=‘ ) 74 { 75 xx = find(x[i]); 76 yy = find(y[i]); 77 if(xx!=yy) 78 { 79 father[xx] = yy; 80 cnt --; 81 } 82 } 83 } 84 for( int i = 0 ; i<m ; i++ ) 85 { 86 if( ch[i] == ‘=‘ ) 87 continue; 88 xx = find(x[i]); 89 yy = find(y[i]); 90 if( ch[i]==‘>‘ ) 91 { 92 ve[xx].push_back(yy); 93 in[yy] ++; 94 } 95 else 96 { 97 ve[yy].push_back(xx); 98 in[xx] ++; 99 }100 }101 topo( );102 if( CONFLICT )103 cout << "CONFLICT" << endl;104 else if( UNCERTAIN )105 cout << "UNCERTAIN" << endl;106 else107 cout << "OK" << endl;108 }109 return 0;110 }
1 //1. 当入队的个数 >1 时证明拓扑排序结果不唯一 uncertain 2 //2. 入队进行拓扑排序的元素 < 总共的元素个数 成环的存在 conflict 3 #include <iostream> 4 #include <cstring> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 9 int n , cnt; 10 bool CONFLICT , UNCERTAIN; 11 const int size = 10010; 12 int in[size]; 13 int father[size]; 14 vector<int>ve[size]; 15 queue<int>q; 16 17 void init( ) 18 { 19 memset( father , -1 , sizeof(father) ); 20 memset( in , 0 , sizeof(in) ); 21 for( int i = 0 ; i<size ; i++ ) 22 { 23 ve[i].clear(); 24 } 25 } 26 27 int find( int x ) 28 { 29 return father[x] == -1 ? x : father[x] = find( father[x] ); 30 } 31 32 void topo( ) 33 { 34 for( int i = 0 ; i<n ; i++ ) 35 { 36 if( !in[i] && father[i] == -1 ) 37 { 38 q.push(i); 39 } 40 } 41 while( !q.empty() ) 42 { 43 if( q.size()>1 ) 44 UNCERTAIN = true; 45 int now = q.front(); 46 q.pop(); 47 cnt --; 48 for( int i = 0 ; i<ve[now].size() ; i++ ) 49 { 50 int u = ve[now][i]; 51 if( --in[u] == 0 ) 52 { 53 q.push(u); 54 } 55 } 56 } 57 if( cnt>0 ) 58 CONFLICT = true; 59 } 60 61 int main() 62 { 63 int m , x , y; 64 char ch; 65 while( cin >> n >> m ) 66 { 67 init( ); 68 cnt = n;//原来的元素总数 69 CONFLICT = UNCERTAIN = false;//1是关于conflice 2是关于uncertain 70 while( m-- ) 71 { 72 cin >> x >> ch >> y; 73 x = find(x); 74 y = find(y); 75 if( ch==‘=‘ ) 76 { 77 if(x!=y) 78 { 79 father[x] = y; 80 cnt --; 81 } 82 } 83 else if( ch==‘>‘ ) 84 { 85 ve[x].push_back(y); 86 in[y] ++; 87 } 88 else 89 { 90 ve[y].push_back(x); 91 in[x] ++; 92 } 93 } 94 topo( ); 95 if( CONFLICT ) 96 cout << "CONFLICT" << endl; 97 else if( UNCERTAIN ) 98 cout << "UNCERTAIN" << endl; 99 else100 cout << "OK" << endl;101 }102 return 0;103 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。