# 題目: 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

node 的數量有可能為 0
node 可能連接到自己

	#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;
	}