# Poj Solution 1703

```http://poj.org/problem?id=1703

//* @author: 82638882@163.com
import java.io.*;
public class Main
{
static int[] p,q;
static int u;
public static void main(String[] args) throws IOException
{
while((a--)!=0)
{
int n=Integer.parseInt(ss);
int m=Integer.parseInt(ss);
p=new int[n+1];
q=new int[n+1];
for(int i=0;i<=n;i++)
p[i]=i;
for(int i=0;i< m;i++)
{
int x=Integer.parseInt(ss);
int y=Integer.parseInt(ss);
if(ss.equals("D"))
union(x,y);
else{
if(root(x)!=root(y))
System.out.println("Not sure yet.");
else
{
if(get(x)==get(y))
System.out.println("In the same gang.");
else
System.out.println("In different gangs.");
}
}
}
}
}
static int root(int a)
{
while(p[a]!=a)
a=p[a];
return a;
}
static void union(int x,int y)
{
int s1=get(x);
int x1=u;
int s2=get(y);
int y1=u;
if(x1==y1)return;
if(x1< y1)
{
p[y1]=x1;
if(s1==s2)
q[y1]=q[x1]+1;
}
else
{
p[x1]=y1;
if(s1==s2)
q[x1]=q[y1]+1;
}
}

static int get(int a)
{
int t=0;
while(p[a]!=a)
{
t+=q[a];
a=p[a];
}
u=a;
return t%2;
}
}
```
This entry was posted in poj. Bookmark the permalink.