PAT甲级 1146 Topological Order (25 分) 【拓扑排序】

This is a problem given in the Graduate Entrance Exam in 2018: Which of the following is NOT a topological order obtained from the given directed graph? Now you are supposed to write a program to test each of the options.
PAT甲级 1146 Topological Order (25 分) 【拓扑排序】

Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 1,000), the number of vertices in the graph, and M (≤ 10,000), the number of directed edges. Then M lines follow, each gives the start and the end vertices of an edge. The vertices are numbered from 1 to N. After the graph, there is another positive integer K (≤ 100). Then K lines of query follow, each gives a permutation of all the vertices. All the numbers in a line are separated by a space.

Output Specification:
Print in a line all the indices of queries which correspond to “NOT a topological order”. The indices start from zero. All the numbers are separated by a space, and there must no extra space at the beginning or the end of the line. It is graranteed that there is at least one answer.

Sample Input:

6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6

Sample Output:

3 4

关于拓扑排序：

拓扑排序的应用是判断一个图是否为有向无环图，如果topologicalSort()函数返回true，则说明拓扑排序成功，给定的图是有向无环图；否则，说明拓扑排序失败，给定的图中有环。

求有向图的一个拓扑排序流程：

定义一个队列Q，并把所有入度为0的结点加入队列。
取队首结点，输出。然后删去所有从它出发的边，并令这些边到达的顶点的入度减1，如果某个定点的入度减为0，则将其加入队列。
反复进行2操作，直到队列为空。如果队列为空时入过队的结点数目恰好为N，说明拓扑排序成果，图为有向无环图；否则，拓扑排序失败，图G中有环。

模板：

vector<int> G[maxn];
int n, m, inDegree[maxn];  // 顶点数、入度

// 拓扑排序
bool topologicalSort()
{
	int num = 0;  // 记录加入拓扑序列的顶点数
	queue<int> q;
	for (int i = 0; i < n; i ++)
	{
		if (inDegree[i] == 0) q.push(i);
	}
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int i = 0; i < G[u].size(); i ++)
		{
			int v = G[u][i];
			inDegree[v] --;
			if (inDegree[v] == 0) q.push(v);
		}
	}
	if (num == n) return true;
	return false;
}

判断给定序列是否为有向图的拓扑排序

bool isTopo(vector<int> v)
{
	// 遍历每一个顶点u
    for (auto u : v)
    {
    	// 如果当前顶点u入度不为0，则不是拓扑排序
        if (in[u]) return false;
        // 遍历u临接表的出点，入度减1
        for (auto nxt : E[u]) in[nxt] --;
    }
    return true;
}

题目大意：
给出一个有向图，并给出k个查询，输出所有不是拓扑排序的查查询。
注意：询问序列是从0开始的。

分析：
裸拓扑排序，对于每个序列，要用原始的入度，所以需要对入度作备份

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1010;
const int INF = 0x3f3f3f3f;

vector<int> E[maxn];  // 临接表
int n, m, in[maxn], inBK[maxn]; // 顶点数、入度、入度的备份
vector<int> ans;

// 拓扑排序
bool isTopo(vector<int> v)
{
    for (auto u : v)
    {
        if (in[u]) return false;
        for (auto nxt : E[u]) in[nxt] --;
    }
    return true;
}

int main()
{
    cin >> n >> m;  // n个点，m条边
    for (int i = 0; i < m; i ++)
    {
        int a, b;
        cin >> a >> b;
        E[a].push_back(b);
        in[b] ++;
    }

    int k;
    cin >> k;
    for (int i = 0; i < k; i ++)
    {
        memcpy(inBK, in, (n+1) * sizeof(int));
        vector<int> v(n + 1);
        for (int j = 1; j <= n; j ++) cin >> v[j];
        if (!isTopo(v))
            ans.push_back(i);
        memcpy(in, inBK, (n+1) * sizeof(int));
    }
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << " \n"[i+1==ans.size()];
    return 0;
}

PAT甲级 1146 Topological Order (25 分) 【拓扑排序】

相关推荐