Vijos 小胖的奇偶

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 int n,m;
 7 char ss[105];
 8 int rela[5000005];
 9 int fa[5000005];
10 int find(int x)
11 {
12     if(x==fa[x])return x;
13     int ff=fa[x];
14     fa[x]=find(ff);
15     rela[x]=(rela[x]+rela[ff])%2;
16     return fa[x];
17 }
18 int main()
19 {
20     freopen("xp.in","r",stdin);
21     freopen("xp.out","w",stdout);
22     int i;
23     int left,right;
24     cin>>n>>m;
25     int ans=m;
26     for(i=1;i<=n;i++)fa[i]=i;
27     for(i=1;i<=m;i++)
28     {
29         cin>>left>>right;
30         scanf("%s",ss);
31         left--;
32         if(ss[0]==‘e‘)
33         {
34             int ffl=find(left);
35             int ffr=find(right);
36             if(ffl<ffr)
37             {
38                 fa[ffr]=ffl;
39                 rela[ffr]=(rela[left]-rela[right]+2)%2;
40             }
41             else if(ffl>ffr)
42             {
43                 fa[ffl]=ffr;
44                 rela[ffl]=(rela[right]-rela[left]+2)%2;
45             }
46             else
47             {
48                 if(rela[right]!=rela[left])
49                 {
50                     ans=i-1;
51                     break;
52                 }
53             }
54         }
55         if(ss[0]==‘o‘)
56         {
57             int ffl=find(left);
58             int ffr=find(right);
59             if(ffl<ffr)
60             {
61                 fa[ffr]=ffl;
62                 rela[ffr]=(rela[left]-rela[right]+3)%2;
63             }
64             else if(ffl>ffr)
65             {
66                 fa[ffl]=ffr;
67                 rela[ffl]=(rela[right]-rela[left]+3)%2;
68             }
69             else
70             {
71                 if(rela[right]==rela[left])
72                 {
73                     ans=i-1;
74                     break;
75                 }
76             }
77         }
78     }
79     cout<<ans;
80     return 0;
81 }

 1 #include<iostream>
 2 #include<cstdlib>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<map>
 6 using namespace std;
 7 int n,m;
 8 char ss[105];
 9 int rela[500005];
10 int fa[500005];
11 map<int,int>mp;
12 int find(int x)
13 {
14     if(x==fa[x])return x;
15     int ff=fa[x];
16     fa[x]=find(ff);
17     rela[x]=(rela[x]+rela[ff])%2;
18     return fa[x];
19 }
20 int main()
21 {
22     freopen("xp.in","r",stdin);
23     freopen("xp.out","w",stdout);
24     int i;
25     int left,right;
26     cin>>n>>m;
27     int ans=m;
28     int cnt=0;
29     for(i=1;i<=50005;i++)
30         fa[i]=i;
31     for(i=1;i<=m;i++)
32     {
33         cin>>left>>right;
34         scanf("%s",ss);
35         left--;
36         if(mp[left]==0){cnt++;mp[left]=cnt;}
37         if(mp[right]==0){cnt++;mp[right]=cnt;}
38         if(ss[0]==‘e‘)
39         {
40             int ffl=find(mp[left]);
41             int ffr=find(mp[right]);
42             if(ffl<ffr)
43             {
44                 fa[ffr]=ffl;
45                 rela[ffr]=(rela[mp[left]]-rela[mp[right]]+2)%2;
46             }
47             else if(ffl>ffr)
48             {
49                 fa[ffl]=ffr;
50                 rela[ffl]=(rela[mp[right]]-rela[mp[left]]+2)%2;
51             }
52             else
53             {
54                 if(rela[mp[right]]!=rela[mp[left]])
55                 {
56                     ans=i-1;
57                     break;
58                 }
59             }
60         }
61         if(ss[0]==‘o‘)
62         {
63             int ffl=find(mp[left]);
64             int ffr=find(mp[right]);
65             if(ffl<ffr)
66             {
67                 fa[ffr]=ffl;
68                 rela[ffr]=(rela[mp[left]]-rela[mp[right]]+3)%2;
69             }
70             else if(ffl>ffr)
71             {
72                 fa[ffl]=ffr;
73                 rela[ffl]=(rela[mp[right]]-rela[mp[left]]+3)%2;
74             }
75             else
76             {
77                 if(rela[mp[right]]==rela[mp[left]])
78                 {
79                     ans=i-1;
80                     break;
81                 }
82             }
83         }
84     }
85     cout<<ans;
86     return 0;
87 }