1 #include"iostream" 2 #include"cstdio" 3 #include"cstring" 4 #include"map" 5 using namespace std; 6 const int N = 5010; 7 int rt[N<<1],w[N<<1];   //带权（种类）并查集 begin，end 8 map<int,int> mp;    //离散化，begin 9 int tot;    //离散化，end10 int n,m,l,r;    //输入，begin11 char str[10];   //输入，end12 13 void paco(int a)14 {15     if(rt[a]==a) {  //分治终点16         return ;17     }18     paco(rt[a]);    //分治19     w[a] ^= w[rt[a]];   //回溯，begin 注：树根的w一定为0,我们只在意树边上的信息即可20     rt[a] = rt[rt[a]];     //回溯，end 注：我们只在意树边上的信息即可21 }22 23 bool unio(int a,int b,int cnd)  //路径压缩 + 条件判断（合法性判断+树的合并）24 {25     paco(a);26     paco(b);27     int rt_a = rt[a],rt_b = rt[b];28     if(rt_a==rt_b) {29         return w[a]^w[b]^(!cnd);    //搞个卡诺图化简一下30     }31     else {32         rt[rt_a] = rt_b;33         w[rt_a] = (w[a]+w[b]+cnd)&1;    //搞个状态转换图推一下，因为树根的w为0，所以两根之间的关系就是新树边的w值 注：我们只在意树边上的信息即可34     }35     return true;36 }37 38 int main()39 {40     int i,res;41     bool ok;42     while(scanf("%d",&n)!=EOF&&n!=-1) {43         scanf("%d",&m);44         for(i = 0; i<=m; ++i) {45             rt[i] = i;46         }47         memset(w,0,sizeof(int)*(m+1));48         mp.clear();49         tot = 1;50         res = 0;51         ok = 1;52         for(i = 1; i<=m; ++i) {53             scanf("%d%d%s",&l,&r,str);54             if(mp.find(l-1)==mp.end()) {    //离散化，begin55                 mp[l-1] = tot++;56             }57             if(mp.find(r)==mp.end()) {58                 mp[r] = tot++;59             }                               //离散化，end60             if(unio(mp[l-1],mp[r],str[0]==‘o‘)) {61                 if(ok) {62                     ++res;63                 }64             }65             else {66                 ok = 0;67             }68         }69         printf("%d\n",res);70     }71     return 0;72 }