Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

把我的search和union帖出来算了。。看看是不是有问题？

Posted by pfz1stp at 2007-06-02 16:27:44 on Problem 2236
In Reply To:那就不是DS的问题了，肯定你的算法不好了。。。 Posted by:richardxx at 2007-06-02 16:16:39

	int search(int x)
	{
		int f=x;
		while (par[f]!=-1)
		{
			f=par[f];
		}
		int ff=x;
		while (ff!=f)
		{
			int tf=ff;
			ff=par[ff];
			par[tf]=f;
		}
		return f;
	}

	bool sunion(int x, int y)
	{
		int r1=search(x);
		int r2=search(y);
		if (r1!=r2)
		{
			if (rank[r1]>rank[r2])
			{
				par[r2]=r1;
				rank[r1]++;
			}
			else
			{
				par[r1]=r2;
				rank[r2]++;
			}
			return 1;
		}
		return 0;
	}

Followed by:

觉得没问题，差不多这么写，不要怀疑DS了，怀疑算法吧。。。 (4) richardxx 2007-06-02 17:09:38
- 这两个题都没有什么算法可言啊。。 (17) pfz1stp 2007-06-02 17:22:30
  - 有的，比如一些归并的策略就比其它的好。。。 (21) richardxx 2007-06-02 18:24:33

Post your reply here:

Home Page Go Back To top