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

请高手指点,小弟一直wa。。。。。。

Posted by LGQ at 2008-05-14 17:01:40 on Problem 2492
#include <stdio.h>
#include <string.h>

int p[1000001], opp[1000001], rank[1000001], m, n;

int find(int x){
	if(x == -1)
		return -1;
	if(p[x] != x)
		p[x] = find(p[x]);
	return p[x];
}

int Union(int x, int y){
	if(x == -1)
		return y;
	else if(y == -1)
		return x;
	else{
		x = find(x);
		y = find(y);
		if(rank[x] > rank[y]){
			p[y] = x;
			return x;
		}
		else{
			p[x] = y;
			if(rank[x] == rank[y])
				rank[y]++;
			return y;
		}
	}
}

int different(int x, int y){
	int tx, ty;
	x = find(x);
	y = find(y);
	tx = Union(opp[x], y);
	ty = Union(x, opp[y]);
	opp[tx] = ty;
	opp[ty] = tx;
}

int main(){
	freopen("2223.in", "r",stdin);
	int i, j, a, b, x, y, f, xxx, c, t = 1;
	scanf("%d", &c);
	while(c--){
		scanf("%d%d", &m, &n);
		printf("Scenario #%d:\n", t);
		for(i = 1; i <= m; i++){
			p[i] = i;
			opp[i] = -1;
			rank[i] = 0;
		}
		xxx = f = 0;
		for(i = 1; i <= n; i++){
			scanf("%d%d", &a, &b);
			x = find(a);
			y = find(b);
			if(x == y){
				printf("Suspicious bugs found!\n");
				f = 1;
				break;
			}
			different(a, b);
		}
		if(!f){
			printf("No suspicious bugs found!\n");
		}
		t++;
		putchar('\n');
	}
	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