当前位置：首页 > news >正文

hdu--1811--并查集拓扑排序好题

news 来源：原创 2024/4/27 19:29:49

做了这题绝逼累啊..

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;//conflict
101                 }
102             }
103         }
104         topo();
105         if (flag)
106             cout << "CONFLICT" << endl;
107         else
108         {
109             if (ans)
110                 cout << "UNCERTAIN" << endl;
111             else
112                 cout << "OK" << endl;
113         }
114     }
115     return 0;
116 }

View Code

  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         else
107             cout << "OK" << endl;
108     }
109     return 0;
110 }

View Code

  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         else
100             cout << "OK" << endl;
101     }
102     return 0;
103 }