(题目链接)
题意
中文题
Solution
带权并查集。
fa记录父亲，r记录与父亲的关系。%3运用的很巧妙。
代码
// poj1182#include#include #include #include #include #include #define LL long long#define inf 2147483640#define Pi 3.1415926535898#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;int fa[1000010],r[1000010],n,k;int find(int x) { if (x!=fa[x]) { int fx=find(fa[x]); r[x]=(r[x]+r[fa[x]])%3; fa[x]=fx; } return fa[x];}bool Union(int x,int y,int type) { int fx,fy; fx=find(x);fy=find(y); if (fx==fy) { if ((r[y]-r[x]+3)%3!=type) return 1; else return 0; } fa[fy]=fx; r[fy]=(r[x]-r[y]+type+3)%3; return 0;}int main() { scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) fa[i]=i; memset(r,0,sizeof(r)); int sum=0; while (k--) { int d,x,y; scanf("%d%d%d",&d,&x,&y); if (x>n || y>n || (x==y && d==2)) sum++; else if (Union(x,y,d-1)) sum++; } printf("%d",sum); return 0;}