首页 > 代码库 > uva-10305-水题-拓扑排序

uva-10305-水题-拓扑排序

输入n,m,n代表点数,m代表边数(i,j),排序时i在j前面,没出现的点随意排

#include <iostream>#include<stdio.h>#include<math.h>#include<memory.h>using namespace std;const int maxNum = 120;int a, b;int map[maxNum][maxNum];int vis[maxNum];int index2;int res[maxNum];bool topoSort(int row){	vis[row] = -1;	for (int i = 1; i <= a; i++)	{		if (vis[i] == -1 && i != row)			 continue;		else if (map[row][i] == 1 && vis[i] == 0)		{			topoSort(i);		}	}	res[++index2] = row;	vis[row] = 1;	return true;}int main(){		while (cin >> a >> b)	{		if(a == b && b == 0)		{			return 0;		}		index2 = 0;		memset(map, 0, sizeof(map));		memset(vis, 0, sizeof(vis));		int j, k;		for (int i = 0; i < b; i++)		{			cin >> j >> k;			//前向边			map[j][k] = 1;		}		for (int i = 1; i <= a; i++)		{			if (vis[i] == 0)				topoSort(i);		}		for (int i = a; i >= 1; i--)		{			if (i == a)			{				cout << res[i];				continue;			}			cout << " " << res[i];		}		cout << endl;	}	return 0;}

  

uva-10305-水题-拓扑排序