URAL/1003

来自"NOCOW"

#include<iostream>
#include<string>
const int BLOCK=10000;
const int HASHTHING=6000;
int hashTable[20000];
int father[20000]; //0..9999 , 10000..19999
int Hash(int number)
{
    int pos=number % HASHTHING;
    while(hashTable[pos]!=-1 && hashTable[pos]!=number) pos=(pos+1)%HASHTHING;
    hashTable[pos]=number;
    return pos;
}
int Find(int x)
{
    int root=x;
    while(root!=father[root]) root=father[root];
    while(x!=root)
    {
        int temp=father[x];
        father[x]=root;
        x=temp;
    }
    return root;
}
void Union(int x,int y)
{
    int p=Fnd(x);
    int q=Find(y);
    if (p!=t)
        father[p]=q;
}
int main()
{
    while(true)
    {
        int len;
        std::cin>>len;
        if(len==-1) break;
 
        int n;
        std::cin>>n;
        memset(hashTable,0xff,sizeof(hashTable));
        for(int i=0;i<20000;++i) father[i]=i;
 
        int count;
        for(count=1;count<=n;++count)
        {
            int a,b;
            std::string signal;
            std::cin>>a>>b>>signal;
            bool even=(signal=="even");
            a=Hash(a-1);
            b=Hash(b);
 
            if(even)
            {
                if(Find(a)==Find(b+BLOCK)) break;
                Union(a,b);
                Union(a+BLOCK,b+BLOCK);
            }else{ //odd
                if(Find(a)==Find(b)) break;
                Union(a,b+BLOCK);
                Union(a+BLOCK,b);
            }
        }
        int ans=count-1;
        {
        int tempa,tempb;std::string tempstr;
        for(++count;count<=n;++count)
            std::cin>>tempa>>tempb>>tempstr;
        }
        std::cout<<ans<<std::endl;
    }
    return 0;
}

program Parity;
  const
    maxm=65535;
  var
    fa,h:array[0..maxm shl 1]of longint;
    n,m,i,x,y,ans:longint;
    c:char;
    bb,b:boolean;
  function ha(i:longint):longint;
    var
      j:longint;
    begin
      j:=i mod maxm;
      while(h[j]<>-1)and(h[j]<>i)do
        j:=(j+1)mod maxm;
      h[j]:=i;
      ha:=j;
    end;
  function find(x:longint):longint;
    var
      tmp:longint;
    begin
      if x=fa[x]
        then exit(x);
      if fa[x]=fa[fa[x]]
        then exit(fa[x]);
      tmp:=find(fa[x]);
      fa[x]:=tmp;
      find:=tmp;
    end;
  procedure union(x,y:longint);
    begin
      x:=find(x);
      y:=find(y);
      if x<>y
        then fa[x]:=y;
    end;
  begin
    readln(n);
    while n+1<>0do
      begin
        for i:=0 to maxm shl 1 do
          begin
            fa[i]:=i;
            h[i]:=-1;
          end;
        readln(m);
        bb:=true;
        b:=true;
        ans:=0;
        for i:=1 to m do
          begin
            readln(x,y,c,c);
            if b
              then begin
                x:=ha(x-1);
                y:=ha(y);
                inc(ans);
                if c='e'
                  then begin
                    if find(x)=find(y+maxm)
                      then begin
                        bb:=false;
                        b:=false;
                        continue;
                      end;
                    union(x,y);
                    union(x+maxm,y+maxm);
                  end
                  else begin
                    if find(x)=find(y)
                      then begin
                        bb:=false;
                        b:=false;
                        continue;
                      end;
                    union(x,y+maxm);
                    union(x+maxm,y);
                  end;
              end;
          end;
        dec(ans);
        if(ans+1=m)and bb
          then inc(ans);
        writeln(ans);
        readln(n);
      end;
  end.