C++拓扑排序题目

本文主要是介绍C++拓扑排序题目，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Description

学校里开设了n门课，其编号为0、1、2、……、n-1，但是有些课程需要完成其它课程才能学习。
小s是一个卷王，他不学完所有课程就不高兴。但是安排课程的老师犯了一些错误，导致有些课程可能不能学习。比如课程0、1，课程0需要学完课程1才能学，课程1需要学完课程0才能学，则课程0、1都不能学。
小s想要知道他最多能学多少门课。

Input

第一行一个int型整数T，代表一共有T组数据。
对于每组数据，第一行一个整数n（n<=10000）和一个整数m（m<=10000）。接下来m行，每行两个整数x，y（0<=x,y<n），表示学课程y前必须学完课程x。

Output

输出T行, 每行包括一个整数, 代表每组数据小s最多能学的课程数。

Sample Input

1
6 5
0 1
1 2
2 3
3 1
2 4

Sample Output

2

结果代码：

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct AdList
{
	vector<int>next;
};
int main()
{
	int T = 0;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		int n, m;
		cin >> n; cin >> m;
		int* count = new int[n];
		vector<int>root;
		for (int i = 0; i < n; i++)
		{
			count[i] = 0;
		}
		AdList* adlist = new AdList[n];
		for (int i = 0; i < m; i++)
		{
			int x, y;
			cin >> x;
			cin >> y;
			count[y]++;
			adlist[x].next.push_back(y);
		}
		for (int i = 0; i < n; i++)
			if (count[i] == 0)root.push_back(i);
		for (vector<int>::iterator it = root.begin(); it != root.end(); it++)
		{
				queue<int>q;
		        q.push(*it);
				while (!q.empty())
				{
					int p = q.front(); q.pop();
					int j = 0;
					for(vector<int>::iterator t= adlist[p].next.begin(); t!= adlist[p].next.end();t++,j++ )
					{
						int k = adlist[p].next[j];
							count[k]--;
							if (count[k] == 0)q.push(k);
						
					}
				}
		}
		int result = 0;
		for (int i = 0; i < n; i++)
		{
			if (count[i] == 0)result++;
		}
		cout << result << endl;
		delete[]count;
		delete[]adlist;
	}
	return 0;
}

这篇关于C++拓扑排序题目的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！