Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

提供我的代码,仅供参考。

Posted by zerocpp at 2011-04-03 00:40:37 on Problem 1611
In Reply To:并查集老是WA,哪位帮忙看下代码。。 Posted by:yayu_myself at 2009-12-27 10:44:03
//AC, 0ms, G++
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
using namespace std;
#define M 30010
int d[M];//disjoint set
int n, m;
int f(int x)
{
	int r = x;
	while (d[r] != r) r = d[r];
	int t;
	while (d[x] != r) t = d[x], d[x] = r, x = t;
	return r;
}
void u(int x, int y)
{
	x = f(x);
	y = f(y);
	if (!x) d[y] = x;
	else d[x] = y;
}
bool func()
{
	scanf("%d%d", &n, &m);
	if (!n && !m) return 0;
	for (int i = 0; i < n; ++ i) d[i] = i;
	while (m --)
	{
		int k;
		scanf("%d", &k);
		if (!k) continue;
		int n1;
		scanf("%d", &n1);
		while (-- k)
		{
			int n2;
			scanf("%d", &n2);
			u(n2,n1);
		}
	}
	return 1;
}
int main()
{
	while (func())
	{
		int cnt = 0;
		for (int i = 0; i < n; ++ i)
			if (!f(i)) ++ cnt;
		printf("%d\n", cnt);
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator