poj1703

此題考查并查集用輔助數組标記分類 關鍵點在于路徑壓縮時候對于葉子節點的處理，了解了就很容易畢竟AC的人很多

if (ans[Father[x]] == true)

ans[x] = !ans[x];

關鍵點在這句話

#include<iostream>  

#include<fstream>

using namespace std;

int Father[100005];

int Case=0;

bool ans[100005];

int Find(int x)

{

if (Father[x] == x) return x;

int root = Find(Father[x]);

if (ans[Father[x]] == true)

ans[x] = !ans[x];

Father[x] = root;

return root;

}

void Un_tree(int x, int y)

{

int rx = 0, ry = 0;

rx = Find(x);

ry = Find(y);

if (rx == ry)return;

Father[ry] = rx;

ans[ry] = (ans[x]==ans[y])?!ans[ry]: ans[ry];

}

int main()

{

//fstream cin("Text.txt");

cin >> Case;

int n=0, m=0;

int man1, man2;

char C;

  while (Case--)

  {

cin >> n >> m;

for (int i = 1; i < n+1;i++)

{

Father[i] = i;

ans[i] = false;

}

for (int i = 0; i < m;i++)

{

scanf("%s%d%d", &C, &man1, &man2);

if (C=='A')

{

if (n == 2)

{ 

cout << "In different gangs." << endl; exit(0); 

}

if (Find(man1) != Find(man2))cout << "Not sure yet." << endl;

else if (ans[man1]==ans[man2])

{

cout << "In the same gang." << endl;

}

else

{

cout << "In different gangs." << endl;

}

}

else

{

Un_tree(man1, man2);

}

}

  }

return 0;

}