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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[codevs 1001] 편안 한 코스.뭐... 이 문 제 를 풀 수 있 을까요? 우리 엄마................................................................................ 나 는 약속 을 하...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.