并查集好經(jīng)典的應(yīng)用，搞明白這個(gè)題目，可以秒殺POJ所有并查集題目!
struct node{
int father;根節(jié)點(diǎn)
int relation;與根節(jié)點(diǎn)關(guān)系:0 同類，1吃根節(jié)點(diǎn)，2被吃
} line[maxn];
int find(int x)
{
if (x!=line[x].father)
{
int tmp=line[x].father;
line[x].father=find(tmp);
//找規(guī)律，求出公式
num[x]=(line[x].relation+line[tmp].relation) % 3;
}
returen line[x].father;
}
void union(int x,int y,int d)
{
int fx=find(x);
int fy=find(y);
line[fx].father=fy;
//找規(guī)律，求出公式
line[fx].relation=(line[y].relation-line[x].relation+2+d) % 3;
return ;
}
Thinking && Coding！！！
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define swap(t,x,y) (t=x,x=y,y=t)
#define clr(list) memset(list,0,sizeof(list))
#define maxn 50005
using namespace std;
int father[maxn];
int num[maxn];
int find(int x)
{
if (x!=father[x])
{
int tmp=father[x];
father[x]=find(father[x]);
num[x]=(num[x]+num[tmp]) % 3;
}
return father[x];
}
void union_set(int x,int y,int d)
{
int fx=find(x);
int fy=find(y);
father[fx]=fy;
num[fx]=(num[y]-num[x]+2+d) % 3;
return ;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int ans=0;
int flag=0;
for (int i=1; i<=n; i++)
father[i]=i,num[i]=0;
for (int i=1; i<=m; i++)
{
int d,x,y;
scanf("%d%d%d",&d,&x,&y);
if (x>n || y>n)
{
ans++;
continue;
}
if (d==2 && x==y)
{
ans++;
continue;
}
int fx=find(x);
int fy=find(y);
if (d==2 && fx==fy)
{
if ((num[x]-num[y]+3)%3!=1)
ans++;
continue;
}
if (d==1 && fx==fy && num[x]!=num[y])
{
ans++;
continue;
}
union_set(x,y,d);
}
printf("%d\n",ans);
return 0;
}