poj 1703 (집합 관 계 를 유지 하 는 방법 을 찾 습 니 다)

/*
translation:
	               ,         ,      。    D a b,  
	a,b            。      A a b,    a,b            
	  。          not sure。      。
solution:
	   。
	       poj1182(   ),                    。      
	      ,           。                 ?      
	      。  unite(a,b)  a,b       ,   unite(a,b+n)   a,b 
	     , a       ,b       。  unite(a+n,b)  a       
	b       。   D   ,      unite。
note:
	*             
date:
	2016.10.17
*/
#include 
#include 
#include 

using namespace std;
const int maxn = 1e5 + 5;

int n, m;
int par[maxn*2], high[maxn*2];

void init(int n)
{
	for(int i = 1; i <= n; i++)
	{
		par[i] = i;
		high[i] = 0;
	}
}

int getRoot(int x)
{
	return par[x] == x ? x : par[x] = getRoot(par[x]);
}

void unite(int x, int y)
{
	x = getRoot(x);
	y = getRoot(y);
	if(x == y)	return;

	if(high[x] < high[y])	par[x] = y;
	else
	{
		par[y] = x;
		if(high[x] == high[y])	high[x]++;
	}
}

bool same(int x, int y)
{
	return getRoot(x) == getRoot(y);
}

int main()
{
	//freopen("in.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--)
	{
		scanf("%d%d", &n, &m);
		init(2*n);

		char op;	int a, b;
		for(int i = 1; i <= m; i++)
		{
			scanf("
%c%d%d", &op, &a, &b); if(op == 'D') { unite(a, b+n); unite(a+n, b); } else { if(same(a, b+n) || same(a+n, b)) printf("In different gangs.
"); else if(same(a, b) || same(a+n, b+n)) printf("In the same gang.
"); else printf("Not sure yet.
"); } } } return 0; }

좋은 웹페이지 즐겨찾기