本文主要是介绍ACMclub - 1122 关系推断 （拓扑排序， 并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目连接
题目描述
给你一些已经确定的元素之间的关系，请你判断是否能从这些元素关系中推断出其他的元素关系。
将小于关系的两个点建立一个边。
拓扑排序：
(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.
(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.
(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.
用并查集判断是否两个点是否有间接过直接的关系。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 30, MAXM = 101;
int T, M, N;
int /*u[MAXN], v[MAXN], first[MAXN], nexte[MAXM],*/ in[MAXN], g[MAXN][MAXN], ok[MAXN];
int p[MAXN];
int find(int x){return p[x] == x ? x : p[x] = find(p[x]);}
void unite(int x, int y) { x = find(x), y = find(y), p[x] = y;}
bool cmp (const int a, const int b) { return a < b;}
vector<int> ans[MAXN];
int topo()
{for(int i = 0; i < N; i++) ans[i].clear();int flag = 0;int r[MAXN];for(int i = 0; i < N; i++) r[i] = i;for(int k = 0; k < N; k++){//找0点int i = 0;while(in[i]!=0 || !ok[i]) i++;//推断关系for(int j = 0; j < N; j++)if(in[j] > in[i] && g[i][j]==0 && find(i) == find(j)){//printf("%c<%c\n", i+'A', j+'A');flag = 1;ans[i].push_back(j);}//减入度in[i]--;for(int j = 0; j < N; j++)if(g[i][j])in[j]--;}return flag;
}int main()
{//freopen("in.txt", "r", stdin);scanf("%d", &T);for(int i = 1; i <= T; i++){printf("Case %d:\n", i);N = 0;scanf("%d", &M);memset(in, 0, sizeof(in));memset(g, 0, sizeof(g));memset(ok, 0, sizeof(ok));for(int i = 0; i < MAXN; i++) p[i] = i;//memset(first, -1, sizeof(first));for(int j = 0; j < M; j++){int u, v;char s[10];scanf("%s", s);if(s[1] == '<')//u[i] = s[1]-'A', v[i] = s[2]-'A';u = s[0]-'A', v = s[2]-'A';else //u[i] = s[2]-'A', v[i] = s[1]-'A';u = s[2]-'A', v = s[0]-'A';//nexte[i] = first[u[i]];//first[u[i]] = i;//g[u[i]][v[i]] = 1;//in[v[i]]++;//N = max(u[i]+1, v[i]+1);g[u][v] = 1;in[v]++;N = max(N, max(u, v)+1);unite(u, v);ok[u] = 1, ok[v] = 1;}if(!topo()) printf("NONE\n");else{for(int i = 0; i < N; i++)for(unsigned int j = 0; j < ans[i].size(); j++)printf("%c<%c\n", i+'A', ans[i][j]+'A');}}return 0;
}
用队列实现拓扑排序
queue<int> que;for(int i = 0; i < N; i++)if(in[i]==0 && ok[i])que.push(i);while(que.size()){int i = que.front(); que.pop();//推断关系for(int j = 0; j < N; j++)if(in[j] > in[i] && g[i][j]==0 && find(i) == find(j)){//printf("%c<%c\n", i+'A', j+'A');flag = 1;ans[i].push_back(j);}//减入度in[i]--;for(int j = 0; j < N; j++)if(g[i][j]){if(--in[j]==0)que.push(j);}}这篇关于ACMclub - 1122 关系推断 （拓扑排序， 并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
