# 題目: UVa 615 - Is It A Tree

# 題目說明

給你一串node的連結關係，求是否為一個tree

---

INPUT:
每筆資料連續輸入兩個整數u與v，代表u連結到v
當u與v皆為0時，結束這筆資料
當u與v皆小於0時，結束程式

---

OUTPUT:
輸出Case x is a tree.或Case 1 is not a tree.

# 解題方法

先用map建雙向的圖
對每一個點跑dfs，若一個點已經走過則忽略
從main呼叫dfs的次數為連通圖的數目 (若大於1則不是tree)
dfs裡，若有cycle，則不是tree

# 參考程式碼

#include <iostream>
#include <map>
#include <vector>

using namespace std;

map<int, vector<int>> G;
map<int, int> vis;
int root;

void dfs(int p, int u)
{
	++vis[u];

	for (auto& v : G[u]) if (v != p)
	{
		if (!vis[v]) dfs(u, v);
		else ++root;

		if (root > 1) return;
	}
}

int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int u, v, cases = 0;	

	while (cin >> u >> v, u >= 0)
	{
		// init
		G.clear();
		vis.clear();
		root = 0;

		while (u)
		{
			G[u].emplace_back(v);
			G[v].emplace_back(u);
			cin >> u >> v;
		}

		for (auto& [u, v] : G) if (!vis[u])
		{
			++root;
			dfs(-1, u);
		}

		cout << "Case " << ++cases << " is" << (root < 2 ? "" : " not") << " a tree.\n";
	}

	return 0;
}