## EDITORWARS 질문드립니다.

• KIMMUSIC

groupe[x][0] 으로 x의 적을 관리 했습니다 웬만한 예제들 생각해서 다 넣어봤을때는 잘 나왔는데 오답으로 뜨네요 어디가 틀린건지 알수 있을까요..

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;

vector<int> parent;
vector<int> Rank;
int groupe[10001][1];

int Find(int x)
{
if (x == -1)
{
return -1;
}
if (x == parent[x])
{
return x;
}
else
{
return parent[x] = Find(parent[x]);
}
}

void merge(int x, int y)
{
x = Find(x);
y = Find(y);

if (x == y)
{
return;
}

if (Rank[x] > Rank[y]) swap(x, y);

parent[x] = y;
if (groupe[x][0] != -1 && groupe[y][0] != -1)
{
merge(groupe[x][0], groupe[y][0]);
}
if(groupe[x][0] == -1)
groupe[x][0] = groupe[y][0];
if (groupe[y][0] == -1)
groupe[y][0] = groupe[x][0];

if (Rank[x] == Rank[y]) Rank[y]++;
}

int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);

int testN;
cin >> testN;
while (testN--)
{
int N, M;
int res = 0;
int visited2[10001] = { 0, };
int resv[10001] = { 0, };
int flag = 0;
memset(groupe, -1, sizeof(groupe));
cin >> N >> M;
parent.clear();
Rank.clear();
parent.resize(N);

for (int i = 0; i < N; ++i)
{
parent[i] = i;
}

Rank.resize(N);

for (int i = 1; i <= M; ++i)
{
string VOE;
int a, b;

cin >> VOE >> a >> b;

if (VOE == "ACK")
{

if (Find(groupe[Find(a)][0]) == Find(b) || Find(groupe[Find(b)][0]) == Find(a))
{
cout << "CONTRADICTION AT " << i << endl;
flag = 1;
continue;
}

merge(a, b);
}

if(VOE == "DIS")
{
int Pa = Find(a);
int Pb = Find(b);

if (Pa == Pb)
{
cout << "CONTRADICTION AT " << i << endl;
flag = 1;
continue;
}

if (groupe[Pa][0] == -1)
groupe[Pa][0] = Pb;

else
{
merge(groupe[Pa][0], Pb);
}

if (groupe[Pb][0] == -1)
{
groupe[Pb][0] = a;
}
else
{
merge(groupe[Pb][0], Pa);
}
}
}

for (int i = 0; i < N; ++i)
{
resv[Find(i)]++;
}

for (int i = 0; i < N; ++i)
{
int k = Find(i);
if (!visited2[k])
{
visited2[k] = 1;
if (groupe[k][0] != -1) {

res += max(resv[k], resv[Find(groupe[k][0])]);
visited2[k] = visited2[Find(groupe[k][0])] = 1;
}

else
{
res += resv[k];
}

}

}
if(flag != 1)
cout <<"MAX PARTY SIZE IS " << res << endl;
}
}


3년 전
##### 0개의 댓글이 있습니다.
• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.