hdoj1811(拓扑排序和并查集)

题目大意

• 给定N个人，从0到N-1编号，编号越大RP越高。
• 给定M个排名关系，如"A > B","A = B","A < B"，分别表示A的Rating高于B,等于B,小于B。
• 根据给定的排名关系对N个人进行排序，排序的规则是按Rating从高到低排序，Rating相同时按RP从高到低排序。
• 问给定的信息是否能确定排序，是的话输出“OK”。否则分析不能确定的原因，是因为信息不完全（输出"UNCERTAIN"），还是因为这些信息中包含冲突（输出"CONFLICT"）

知识背景

• 并查集
  并查集能对元素进行分组，这题利用并查集将人按照Rating是否相同分组，Rating相同的人放在同一组。
  组内每个人的排名已经确定了，因为每个人的编号都不一样，Rating相同的情况下，编号越大排名越高。
  我们接下来需要对组间进行排序
• 拓扑排序
  拓扑排序可以用在这样的情形：
  给定一些点和他们之间的若干大小关系，对这些点进行排序，判断
  • 是否能进行排序
  • 是否存在关系不确定的情况
  • 是否存在关系冲突的情况
    将这些点和他们之间的大小关系用图来表示，用图上的节点表示这些点，用有向边表示这些点的关系，有向边(u, v)表示u比v大。
  • 如果每次入队列时入度节点为0的点不止一个，则说明存在关系不确定
  • 如果入队列的点不等于点的数目，则说明存在环路，关系有冲突

AC代码

#include <iostream>
#include <queue>
using namespace std;

const int MAX_E = 20010;
const int MAX_V = 10010;

//graph presentation
struct Edge{
    int to;
    int next;
};
struct Edge edges[MAX_E];
int head[MAX_V];
int cnt;

//unionfind
int p[MAX_V];//p[i] means the root if node i
int r[MAX_V];//r[i] means the depth of the tree where node i is in

//graph information
int vNum;
int eNum;

//topological sort
int inDegree[MAX_V];//inDegree[i] means the inDegreee of node i
int n;//n means the num of nodes whose final inDegree is 0
int total;//total means the num of different ranks

//input
int a[MAX_E];
int b[MAX_E];
char relation[MAX_E];

//output
bool conflictFlag;
bool uncertainFlag;

//return the root of x
int Find(int x){
    if(x == p[x]) return p[x];
    else return p[x] = Find(p[x]);
}
//union the trees where x and y are in
void Union(int x, int y){
    int xRoot = Find(x);
    int yRoot = Find(y);Find;
    if(r[xRoot] < r[yRoot]) p[xRoot] = yRoot;
    else{
        p[yRoot] = xRoot;
        if(r[xRoot] == r[yRoot]) r[xRoot]++;
    }
}
//return whether x and y are in the same tree
bool sameRoot(int x, int y){
    return Find(x) == Find(y);
}
//topological sort
void toposort(){
    queue<int> q;
    while(!q.empty()) q.pop();
    
    //the first time to push nodes whose inDegree is 0
    for(int i = 0; i < vNum; i++){
        if(inDegree[i] == 0 && p[i] == i) q.push(i);
    }

    while(!q.empty()){
        //if there are more than 1 node whose inDegree is 0 in the same time
        //we say "UNCERTAIN"
        if(q.size() > 1) uncertainFlag = false;
        int u = q.front(); q.pop();
        n++;
        //update neighbor's inDegree
        for(int i = head[u]; i != -1; i = edges[i].next){
            int v = edges[i].to;
            inDegree[v]--;
            if(inDegree[v] == 0) q.push(v);
        }   
    }
    if(n != total) conflictFlag = false;
}

void addEdge(int u, int v){
    edges[cnt].to = v;
    edges[cnt].next = head[u];
    head[u] = cnt++;
}

void init(){
    total = vNum;
    cnt = 0;
    n = 0;
    conflictFlag = true;
    uncertainFlag = true;
    for(int i = 0; i < vNum; i++){
        head[i] = -1;
        p[i] = i;
        r[i] = 0;
        inDegree[i] = 0;
    }
}

int main(){
    while(scanf("%d %d", &vNum, &eNum) == 2){
        init();
        for(int i = 0; i < eNum; i++){
            scanf("%d %c %d", &a[i], &relation[i], &b[i]);
            //when relation[i] == '=' and a[i] b[i] are not in the same tree
            //Union the trees where a[i] and b[i] are in
            if(relation[i] == '=' && !sameRoot(a[i], b[i])){
                Union(a[i], b[i]);
                total--;
            }
        }
        for(int i = 0; i < eNum; i++){
            int x = Find(a[i]);
            int y = Find(b[i]);
            //when relation[i] == '>', add a edge from a[i]'s root to b[i]'s root 
            if(relation[i] == '>'){
                addEdge(x, y);
                inDegree[y]++;
            }
            //when relation[i] == '<', add a edge from b[i]'s root to a[i]'s root 
            if(relation[i] == '<'){
                addEdge(y, x);
                inDegree[x]++;
            }
        }
        toposort();
        if(conflictFlag && uncertainFlag) printf("OK\n");
        else if(!conflictFlag) printf("CONFLICT\n");
        else printf("UNCERTAIN\n");
    }
    return 0;
}