20140711 eat 并查集

跟食物链完全一样
并查集即可。。
 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 #define N 100100
 5 
 6 int rank[3*N+100];
 7 int par[3*N+100];
 8 int n,m;
 9 
10 void init(int n) {
11     for (int i=1;i<=n;i++) {
12         rank[i]=0;
13         par[i]=i;
14     }
15 }
16 
17 int find(int x) {
18     if (par[x]==x) return x;
19     return par[x]=find(par[x]);
20 }
21 
22 void unite(int x,int y) {
23     x=find(x);  y=find(y);
24     if (x==y) return;
25     if (rank[x]<rank[y]) par[x]=y;
26     else {
27         par[y]=x;
28         if (rank[x]==rank[y]) x++;
29     }
30 }
31 
32 bool same(int x,int y) {
33     return find(x)==find(y);
34 }
35 
36 int main() {
37     scanf("%d%d",&n,&m);
38     int ans=0;
39     init(3*N+10);
40     for (int i=0;i<m;i++) {
41         int k,x,y;
42         scanf("%d%d%d",&k,&x,&y);
43         if (x>N || x<1 || y>N || y<1) continue;
44         if (k==1) {
45             if (x==y) {
46                 ans++;
47                 continue;
48             }
49             if (same(x,y+N) || same(x,y+2*N))
50                 continue;
51             else  {
52                 unite(x,y);
53                 unite(x+N,y+N);
54                 unite(x+2*N,y+2*N);
55                 ans++;
56             }
57         }
58         else {
59             if (x==y) continue;
60             if (same(x,y) || same(x,y+2*N))
61                 continue;
62             else {
63                 unite(x,y+N);
64                 unite(x+N,y+2*N);
65                 unite(x+2*N,y);
66                 ans++;
67             }
68         }
69     }
70     printf("%d",ans);
71 }
View Code