a290: 新手訓練系列 ~ 圖論

解題心得

中規中矩的題目，記得要清空graph再繼續吃新測資。

不過我是看以前上課講義的演算法寫的XD

程式碼

#include <iostream>
#include <queue>
using namespace std;

int graph[801][801] = { 0 };

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, a, b, now;
	while (cin >> n >> m)
	{
		for (int i = 0; i <= n; i++)
			for (int j = 0; j <= n; j++)
				graph[i][j] = 0;
		while (m--)
		{
			cin >> a >> b;
			graph[a][b] = 1;
		}
		cin >> a >> b;

		queue<int> q;
		bool isVisited[801] = { false }, isValid = false;
		q.push(a);
		isVisited[a] = true;
		while (!q.empty())
		{
			now = q.front();
			q.pop();
			for (int i = 1; i <= n; i++)
			{
				if (graph[now][i] == 1 && isVisited[i] == false)
				{
					isVisited[i] = true;
					q.push(i);

					if (i == b)
					{
						isValid = true;
						break;
					}
				}
			}
			isVisited[now] = true;
		}
		if (isValid) cout << "Yes!!!" << endl;
		else cout << "No!!!" << endl;
	}
	return 0;
}