代码功能概述

这段代码的主要功能是判断输入的有向图是否为树。输入以边的形式给出，程序会持续处理多组数据，直到遇到 (-1, -1) 输入。

解题思路

1. 输入处理：
   • 持续读取边的信息，直至遇到 (-1, -1)。每组数据以 (0, 0) 结尾。
   • 利用 map 为每个节点分配一个唯一的编号。
2. 图的构建：
   • 用邻接矩阵 adj 存储图的边信息。
   • 用 fa 数组记录每个节点的父节点。
3. 有效性检查：
   • 若存在重复边，判定图不是树。
   • 找出根节点（即 fa[i] == i 的节点），若不存在根节点，判定图不是树。
4. 深度优先搜索（DFS）：
   • 从根节点开始进行 DFS 遍历。
   • 若存在节点未被访问，或者 DFS 过程中出现环（遇到已访问节点），判定图不是树。
5. 输出结果：
   • 根据判断结果输出每组数据是否为树。

#include<iostream>
#include<cstring>
#include<map>
using namespace std;

bool adj[1000][1000],visit[1000];
int edges[1000][2],fa[1000],nn;
map<int,int> mp;

bool dfs(int p){
	//cout << p << endl;
	if(visit[p])
		return 0;
	
	visit[p] = 1;
	for(int i = 0; i < nn; i++)
		if(adj[p][i]){
		if(dfs(i)==0)
			return 0;
	}
	return 1;
}

int main(){
	int m,n,nc=1;
	while(cin>>m>>n&&m!=-1){
		if(m==n&&m==0){
			cout << "Case " << nc++ << " is a tree." << endl;
			continue;
		}
		mp.clear();
		int cnt = 0;
		edges[cnt][0] = m, edges[cnt][1] = n, cnt++;
		mp[m] = 0, mp[n] = 0;
		memset(adj,0,sizeof(adj));
		memset(visit,0,sizeof(visit));
		while(cin>>m>>n&&(m||n))
			edges[cnt][0] = m, edges[cnt][1] = n, cnt++, mp[m] = mp[n] = 0;
		nn = 0;
		for(map<int,int>::iterator it = mp.begin(); it !=mp.end(); it++)
			it->second = nn++;
		for(int i = 0; i < nn; i++) fa[i] = i;
		bool valid = 1;
		for(int i = 0; i < cnt; i++){
			int u = mp[edges[i][0]], v = mp[edges[i][1]];
			fa[v] = u;
			//cout << u << " " << v << endl;
			if(adj[u][v]){
				valid = 0;
				break;
			}
			adj[u][v] = 1;
		}
		if(valid==0){
			cout << "Case " << nc++ << " is not a tree." << endl;
			continue;
		}
		int rt = -1;
		for(int i = 0; i < nn; i++)
			if(fa[i]==i){
			rt = i;
			break;
		}
		cout << "Case " << nc++ << " is " ;
		if(rt==-1){
			cout <<"not a tree." << endl;
			continue;
		}
		if(dfs(rt)){
			int i = 0;
			for(i = 0; i < nn; i++)
				if(visit[i]==0)
					break;
			if(i==nn)
				cout << "a tree." << endl;
			else
				cout << "not a tree." << endl;
		}
		else
			cout << "not a tree." << endl;
	}
}