UVa10596 - Morning Walk(并查集)

importjava.io.FileInputStream;
importjava.io.InputStreamReader;
importjava.io.BufferedReader;
importjava.io.PrintWriter;
importjava.io.OutputStreamWriter;
importjava.io.StreamTokenizer;
classMain{
publicstaticfinalbooleanDEBUG=false;
publicstaticintN=30;
publicBufferedReadercin;
publicPrintWritercout;
publicStreamTokenizertokenizer;
publicintn, r;
publicint[] p, d;
publicvoidinit()
    {
try {
if (DEBUG) {
cin=newBufferedReader(newInputStreamReader(
newFileInputStream("d:\\OJ\\uva_in.txt")));
            } else {
cin=newBufferedReader(newInputStreamReader(System.in));
            }
cout=newPrintWriter(newOutputStreamWriter(System.out));
tokenizer=newStreamTokenizer(cin);
        } catch (Exceptione) {
e.printStackTrace();
        }
    }
publicStringnext()
    {
try {
tokenizer.nextToken();
if (tokenizer.ttype==StreamTokenizer.TT_EOF)
returnnull;
elseif (tokenizer.ttype==StreamTokenizer.TT_NUMBER) {
returnString.valueOf((int) tokenizer.nval);
            }
returnnull;
        } catch (Exceptione) {
e.printStackTrace();
returnnull;
        }
    }
publicintfind(intx)
    {
returnp[x] ==x?x : (p[x] =find(p[x]));
    }
publicbooleaninput()
    {
Strings=next();
if (s==null) returnfalse;
n=Integer.parseInt(s);
s=next();
r=Integer.parseInt(s);
p=newint[n];
d=newint[n];
for (inti=0; i<n; i++) {
p[i] =i;
d[i] =0;
        }
for (inti=0; i<r; i++) {
s=next();
inta=Integer.parseInt(s);
s=next();
intb=Integer.parseInt(s);
p[find(b)] =find(a);
d[a]++;
d[b]++;
        }
returntrue;
    }
publicvoidsolve()
    {
booleanok=true;
if (n==0||r<=1) ok=false;
introot=find(0);
for (inti=0; i<n&&ok; i++) {
if (d[i] !=0) {
if (find(i) !=root||d[i] %2!=0) {
ok=false;
break;
                }
            }
        }
if (ok) {
cout.println("Possible");
        } else {
cout.println("Not Possible");
        }
cout.flush();
    }
publicstaticvoidmain(String[] args)
    {
Mainsolver=newMain();
solver.init();
while (solver.input()) {
solver.solve();
        }
    }
}