拓扑排序

定义

对一个有向无环图 (Directed Acyclic Graph 简称 DAG) G 进行拓扑排序，是将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若边 <u,v> ∈ E(G)，则 u 在线性序列中出现在 v 之前。通常，这样的线性序列称为满足拓扑次序 (Topological Order) 的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

——百度百科

步骤

由 AOV 网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

1. 选择一个入度为 0 的顶点并输出之；

2. 从网中删除此顶点及所有出边。

   循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

模板

#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;
#define MAXN 10005

int n, m, cnt;  //n 个数, m 个关系, cnt: 存储ans数组的下标
bool mp[MAXN][MAXN];
int indeg[MAXN], ans[MAXN];	//indeg[i]: 第i个点的入度; ans[]: 答案队列
queue <int> q;

void Getmap(void)
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		mp[x][y] = 1;
		indeg[y]++;	//建图, 同时统计入度
	}
}

void topo_sort(void)
{
	for (int i = 1; i <= n; i++)
		if (!indeg[i])
			q.push(i);	//将所有入度为 0 的点入队
	while (!q.empty())	//开始搜索
	{
		int u = q.front();
		ans[++cnt] = u;//入度为0的点记得放到答案队列里, 判断环的核心, 看答案数组是否有 n 个
		q.pop();
		for (int i = 1; i <= n; i++)
			if (mp[u][i])	//删边的操作转化为入度减1
			{
				indeg[i]--;
				if (!indeg[i])	//如果这个点变成入度为 0, 入队列
					q.push(i);
			}
	}
}

int main()
{
	Getmap();
	topo_sort();

	if (cnt < n)//判断是否有环, 答案队列不足即有环
	{
		printf("Circle\n");
		return 0;
	}
	for (int i = 1; i <= n; i++)
		printf("%d\n", ans[i]);

	return 0;

}

GYM 102219 J · Kitchen Plates

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

Description

You are given 5 different sizes of kitchen plates. Each plate is marked with a letter A, B, C, D, or E. You are given 5 statements comparing two different plates, you need to rearrange the plates from smallest size to biggest size. For example: the sizes of these plates.

Input

The input consist of 5 lines. In each line there will be 3 characters, the first and last character will be either A, B, C, D, or E and the middle character will be either > or < describing the comparison between two plates sizes. No two plates will be equal.

Output

The output consist of 55 characters, the sorted order of balls from smallest to biggest plate. Otherwise, if the statements are contradicting print impossibleimpossible. If there are multiple answers, print any of them.

Example Input 1

D>B
A>D
E<C
A>B
B>C

Example Output 1

ECBDA

Example Input 2

B>E
A>B
E>A
C<B
D<B

Example Output 2

impossible

Solution

拓扑排序

Accepted Code

#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;

char str[10], ans[10];
int indegree[10], e[10][10];
bool book[10];

int main()
{
	while (scanf("%s", str) != EOF)
	{
		memset(e, 0, sizeof(e));
		memset(indegree, 0, sizeof(indegree));
		memset(book, 0, sizeof(book));

		if (str[1] == '<')
		{
			indegree[str[0] - 'A']++;
			e[str[2] - 'A'][str[0] - 'A']++;
		}
		else
		{
			indegree[str[2] - 'A']++;
			e[str[0] - 'A'][str[2] - 'A']++;
		}
		for (int i = 1; i <= 4; i++)
		{
			scanf("%s", str);

			if (str[1] == '<')
			{
				indegree[str[0] - 'A']++;
				e[str[2] - 'A'][str[0] - 'A']++;
			}
			else
			{
				indegree[str[2] - 'A']++;
				e[str[0] - 'A'][str[2] - 'A']++;
			}
		}
		int len = 0;

		while (1)
		{
			int temp = 0;
			for (int i = 0; i < 5; i++)
				if (!indegree[i] && book[i] == false)
				{
					temp = 1;
					book[i] = 1;
					ans[len++] = i + 'A';
					for (int j = 0; j < 5; j++)
					{
						if (e[i][j])
						{
							e[i][j]--;
							indegree[j]--;
						}
					}
					break;
				}
			if (!temp)
				break;
		}
		if (len == 5)
		{
			for (int i = len - 1; i >= 0; i--)
				printf("%c", ans[i]);
			printf("\n");
		}
		else printf("impossible\n");
	}


	return 0;

}