hdu1811 Rank of Tetris(拓撲排序+并查集)

Rank of Tetris

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 6920    Accepted Submission(s): 1947

Problem Description

自從Lele開發了Rating系統，他的Tetris事業更是如虎添翼，不久他遍把這個遊戲推向了全球。

為了更好的符合那些愛好者的喜好，Lele又想了一個新點子：他将制作一個全球Tetris高手排行榜，定時更新，名堂要比福布斯富豪榜還響。關于如何排名，這個不用說都知道是根據Rating從高到低來排，如果兩個人具有相同的Rating，那就按這幾個人的RP從高到低來排。

終于，Lele要開始行動了，對N個人進行排名。為了友善起見，每個人都已經被編号，分别從0到N-1,并且編号越大，RP就越高。

同時Lele從狗仔隊裡取得一些（M個）關于Rating的資訊。這些資訊可能有三種情況，分别是"A > B","A = B","A < B"，分别表示A的Rating高于B,等于B,小于B。

現在Lele并不是讓你來幫他制作這個高手榜，他隻是想知道，根據這些資訊是否能夠确定出這個高手榜，是的話就輸出"OK"。否則就請你判斷出錯的原因，到底是因為資訊不完全（輸出"UNCERTAIN"），還是因為這些資訊中包含沖突（輸出"CONFLICT"）。

注意，如果資訊中同時包含沖突且資訊不完全，就輸出"CONFLICT"。

Input

本題目包含多組測試，請處理到檔案結束。

每組測試第一行包含兩個整數N,M(0<=N<=10000,0<=M<=20000),分别表示要排名的人數以及得到的關系數。

接下來有M行，分别表示這些關系

Output

對于每組測試，在一行裡按題目要求輸出

Sample Input

3 3
0 > 1
1 < 2
0 > 2
4 4
1 = 2
1 > 3
2 > 0
0 > 1
3 3
1 > 0
1 > 2
2 < 1      

Sample Output

OK

CONFLICT

UNCERTAIN

Author

linle

Source

​​HDOJ 2007 Summer Exercise（2）​​

Recommend

lcy   |   We have carefully selected several similar problems for you:  

​​1198​​​ 

​​​1829​​​ 

​​​1558​​​ 

​​​1856​​​ 

​​​1285​​ 

​​Statistic​​ | ​​Submit​​ | ​​Discuss​​ | ​​Note​​

又學到了一個新知識 拓撲排序

具體就是：

1先建圖，然後尋找入讀為0的頂點

2：然後找到與這個頂點有關的邊和點，删去邊，點的入度-1

3.繼續尋找下一個入度為0的頂點。。重複2.

對于這道題 用到的知識點 并查集，拓撲排序

并查集是為了處理=的情況，使兩個元素合并集合

拓撲排序處理資訊不完整和沖突

1.如果出現兩個同時入度為0的，并且根是自己就是資訊不完整。

2.至于資訊沖突的情況就是出現了環，這時候會發現查詢入度為0的循環執行不下去了，也就是sum>0.

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
struct node//邊
{
  int a,b;//頂點
  char ch;//運算符
}c[10005];
vector<int>map[10005];//map數組存貯鄰接表
int n,m,sum,in[10005],fa[10005];//in數組表示入度,fa[i]表示頂點i所在集合的根節點
int find(int x)//查找根節點
{
  if(fa[x]!=x) fa[x]=find(fa[x]);
  return fa[x];
}
bool comb(int x,int y)//合并集合
{
  x=find(x);
  y=find(y);
  if(x==y)
  return false;
  else
  {
    fa[y]=x;
    return true;
  }
}
void init()//初始化
{
  for(int i=0;i<n;i++)
  fa[i]=i;
}
void top_sort()//queue實作拓撲排序
{
  queue<int>s;
  int flag=0;
  for(int i=0;i<n;i++)
  {
    if(in[i]==0&&fa[i]==i)
    s.push(i);
  }
  while(!s.empty())
  {
    if(s.size()>1)//即使發現資訊不完整也要繼續運作下去，因為如果資訊同時不完整和沖突都是CONFLICT
    flag=1;
    int pos=s.front();
    s.pop(),sum--;
    for(int i=0;i<map[pos].size();i++)
    {
      in[map[pos][i]]--;
      if(in[map[pos][i]]==0)
      s.push(map[pos][i]);
    }
  }
  if(sum>0) printf("CONFLICT\n");
  else if(flag) printf("UNCERTAIN\n");
  else printf("OK\n");
}
int main()
{
  while(scanf("%d %d",&n,&m)!=EOF)
  {
    sum=n;
    init();
    memset(map,0,sizeof(map));
    memset(in,0,sizeof(in));
    for(int i=0;i<m;i++)
    {
      scanf("%d %c %d",&c[i].a,&c[i].ch,&c[i].b);
      if(c[i].ch=='=')
      {
        if(comb(c[i].a,c[i].b))
        sum--;
      }
    }
    for(int i=0;i<m;i++)
    {
      if(c[i].ch=='=')
      continue;
      int x=find(c[i].a);
      int y=find(c[i].b);
      if(c[i].ch=='>')
      {
        map[x].push_back(y);
        in[y]++;
      }
      else
      {
        map[y].push_back(x);
        in[x]++;
      }
    }
    top_sort();
  }
}