各种找矛盾的题..
下面用种比较好的算法写吧,不用扩展域,权值并查集.
怎么权值查并集呢?首先和上个题目一样,用一个d[x]表示x到根节点的距离.假如距离为偶数就表示同一面.奇数就表示对立面.
#include <bits/stdc++.h> using namespace std; const int N=2e4+5; int n,m; unordered_map<int,int>s; int fa[N],d[N]; int find(int x) { if(fa[x]!=x) { int root=find(fa[x]); d[x]+=d[fa[x]]; fa[x]=root; } return fa[x]; } int get(int x) { if(s.count(x)==0) s[x]=++n; return s[x]; } int main() { for(int i=1;i<=N-5;i++) fa[i]=i; cin>>n>>m; int ans=m; n=0; for(int i=1;i<=m;i++) { int a,b;string c; cin>>a>>b>>c; a=get(a-1);b=get(b); int pa=find(a);int pb=find(b); if(c=="even")//偶数 { if(pa==pb) { if(((d[a]-d[b])%2+2)%2!=0)//有矛盾 { ans=i-1; break; } } else { fa[pa]=pb; d[pa]=d[b]-d[a]; } } else//奇数 { if(pa==pb) { if(((d[a]-d[b])%2+2)%2==0)//有矛盾 { ans=i-1; break; } } else { fa[pa]=pb; d[pa]=d[b]-d[a]+1; } } } cout<<ans<<endl; return 0; }