[UVa] 10305 - Ordering Tasks

題目網址: https://goo.gl/qzWqjr

題意:
(from luckycat)


解法:
拓樸排序。

TAG: DFS, Topological Sort

注意:

程式碼:

	/**
	* Tittle: 10305 - Ordering Tasks
	* Author: Cheng-Shih, Wong
	* Date: 2015/06/12
	*/
	// include files
	#include <bits/stdc++.h>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 105
	typedef vector<int> VI;
	// declarations
	int n, m;
	bool edge[N][N];
	int vis[N];
	bool cycle;
	VI ts;
	// functions
	void input( void )
	{
	clr( edge, false );
	int u, v;
	FOR( i, 1, m ) {
	scanf( "%d%d", &u, &v );
	edge[u][v] = true;
	}
	}
	void dfs( int u )
	{
	if( vis[u]==1 ) {
	cycle = true;
	return;
	}
	if( vis[u] ) return ;
	vis[u] = 1;
	FOR( i, 1, n ) if( edge[u][i] )
	dfs( i );
	vis[u] = 2;
	ts.push_back(u);
	}
	void solve( void )
	{
	clr( vis, 0 );
	ts.clear();
	FOR( i, 1, n ) if( !vis[i] )
	dfs( i );
	ts = VI( ts.rbegin(), ts.rend() );
	bool space = false;
	for( int u : ts ) {
	if( space ) putchar(' ');
	else space = true;
	printf( "%d", u );
	}
	putchar('\n');
	}
	// main function
	int main( void )
	{
	// input
	while( scanf( "%d%d", &n, &m )==2 && (n|m) ) {
	input();
	solve();
	}
	return 0;
	}

view raw 10305 - Ordering Tasks.cpp hosted with ❤ by GitHub