zoj 3761 Easy billiards dfs树

这题如果想到的话,写起来很简单。。
题意:无限大的二维坐标系中有n(0<=n<=2000)个球,可以用一个球沿与x坐标轴或y坐标轴平行的方向打球,如果球A碰到球B,那么球A停在球B的地方,球B以与A相同的方向前进,如果B运动的方向前方没有球了,那么判定球B出局,否则球B会撞到球C,以此类推,但是一个球不能直接出局,它必须是被某个球撞击后出局。
思路:把“相邻的球”(即可以直接撞击的球)连边,可以发现,同一个连通快中的球最后只会剩一个,,所以建图后dfs之,形成dfs树,为了保证一个连通块中的点撞到只剩一个,所以只要从子节点撞向父节点即可(比如,(0,0)、(1,0)、(0,1)三个点,dfs之后(0,0)是父节点,另两个是子节点,如果这时从(0,0)撞向(1,0)或(0,1)就会出错)
代码:

无根树转成有根树

/*
输入无根树的结点总数n,以及n-1条边,输出把点u作为根的有根树的各点的父结点
*/
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define maxn 1010
using namespace std;
vector<int> head[maxn];//用做邻接表
int fa[maxn];
void read_tree()
{
	int n,i;
	int u,v;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d %d",&u,&v);
		head[u].push_back(v);
		head[v].push_back(u);
	}
	return;
}
//以u为根,计算各点的父结点
void dfs(int u,int father)
{
	int i;
	int d=head[u].size();
	for(i=0;i<=d-1;i++)
	{
		if(head[u][i]!=fa)
		{
			fa[i]=u;
			dfs(i,u);
		}
	}
	return;
}
int main()
{
	fa[root]=-1;
	read_tree();
	dfs(root,-1);//以root为根

//system("pause");
return 0;
}

hdoj1232

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1232
一道水题,但一开始还是想错了,开始的想法非常二~~。开始是这样想的:因为一棵树要连通的边数最少也就是当它是最小生成树的时候,也就是n-1.于是我用邻接矩阵存储边,数出已经有几条不同的边(count),然后答案就是n-1-count.
对于我这样的菜鸟来说,初看这个思路好像没问题,其实问题很大,因为只有当已经有的边全部是最小生成树中的边时,答案才正确(前面几组sample好像都符合–!,害我想了半天。。~);否则,如果其中有的边不是最小生成树中的,那么即使最终边数达到n-1,还是有点没有连通。换句话说,只有n-1条构成最小生成树的边才能连通所有点。(或者可以这样认为,只有这些已经有的边之间不存在环时才行)
不知道这样说对不对,可能有错误,望大牛指正^_^
最终用dfs找出所有连通分量,解决此题。(网上搜了下都说这道题是并查集的经典题,可惜我还没学。。)
<突然发现最近博客里的文章都是解题报告了。。最近没学其他技术,只能靠写解题报告撑着了。。~>