学步园

今天狠下心，把并查集学了，方便以后写最短路径算法，结合网上和书本上的方法，总算搞明白大概模板和思路

先找了几题练练，都是套模板，但这题卡住了，一直找不到原因，后来看了别人解题报告，才明白忽略了一个问题

 

题意是：给你一幅图，判断它是否存在回路

要注意：要考虑图拆分为几颗树时，也是不符合的。一开始没考虑到这个问题

 

#include <iostream>
#define MAX 100005
using namespace std;

int parent[MAX];


void Union2(int, int);
int find2(int);

int main()
{
	int n, m;
	int a,b;
	int root_a, root_b;
	int flag;
	
	scanf("%d%d",&a, &b);
	while ( a != -1 && b != -1)
	{
		memset(parent, -1, MAX*sizeof(int));
		flag = true;
		m = 0;
		n = a;
		while (a||b)
		{		
	
			if (parent[a-1] == -1 && parent[b-1] == -1)
				m++;
			else if (parent[a-1] != -1 && parent[b-1] != -1)
				m--;
				
			//查找根结点
			root_a = find2(a-1);
			root_b = find2(b-1);

			//如果两个根节点相同，证明a,b两点已有路相连，再添加边会产生回路
			if (root_a != root_b)		
				Union2(root_a, root_b);
			else
				flag = false;
			scanf("%d%d",&a, &b);
		}
		if (flag && m == 1 || n == 0)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
		scanf("%d%d",&a, &b);
	}
	return 0;
}

//并集，根节点多的做根节点少的父节点
void Union2(int i , int j)
{	
	int temp = parent[i] + parent[j];
	if (parent[i] > parent[j])
	{
		parent[i] = j;
		parent[j] = temp;
	}
	else
	{
		parent[j] = i;
		parent[i] = temp;
	}

}

//查找，运用折叠规则
int find2(int i)
{
	int root, trail,lead;
	for (root = i; parent[root] >= 0; root = parent[root])
		;
	for (trail = i; trail != root; trail = lead)
	{
		lead = parent[trail];
		parent[trail] = root;
	}
	return root;
}