每日算法——并查集的应用

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 
 6 using namespace std;
 7 struct spaceship
 8 {
 9     int father;
10     int len,maxlen;
11     
12     spaceship(){len=0;maxlen=1;}
13 }sp[30010];
14 
15 int get(int n)
16 {
17     if (sp[n].father==n) return n;
18     int m=get(sp[n].father);
19     sp[n].len+=sp[sp[n].father].len;
20     sp[n].father=m;
21     return sp[n].father;
22 }
23 
24 void marry(int n,int m)
25 {
26     int nn=get(n);
27     int mm=get(m);
28     sp[nn].father=mm;
29     sp[nn].len+=sp[mm].maxlen;
30     sp[mm].maxlen+=sp[nn].maxlen;
31 }
32 
33 int main()
34 {
35     int n;
36     scanf("%d",&n);
37     for (int i=1;i<=30000;i++) sp[i].father=i;
38     for (int i=1;i<=n;i++)
39     {
40         char ch;
41         int j,k;
42         char s[5];
43         scanf("%s",s);
44         if (s[0]=='M')
45         {
46             scanf("%d%d",&j,&k);
47             marry(j,k);
48         }
49         else
50         {
51             scanf("%d%d",&j,&k);
52             if (get(j)==get(k))
53             {
54                 printf("%d\n",abs(sp[j].len-sp[k].len)-1);
55             }
56             else
57                 printf("-1\n");
58         }
59     }    
60     return 0;
61 }

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 
 6 using namespace std;
 7 struct star
 8 {
 9     int father;
10     int len;
11 
12     star()
13     {
14         father=0;
15         len=0;
16     };
17 }st[100010];
18 int mod;
19 int get(int now)
20 {
21     if (st[now].father==now)
22     {
23         return now;
24     }
25     int f=get(st[now].father);
26     st[now].len=(st[now].len+st[st[now].father].len)%mod;
27     if (st[now].len==0) st[now].len=mod;
28     st[now].father=f;
29     return f;
30 }
31 void marry(int a,int b,int l)
32 {
33     int bf=get(b);
34     int af=get(a);
35     int len=st[a].len+l;
36     len=len % mod;
37     if (l>=st[b].len)
38     {
39         st[bf].father=a;
40         st[bf].len=l-st[b].len;
41     }
42     else
43     {
44         st[bf].father=a;
45         st[bf].len=mod+l-st[b].len;
46     }
47 }
48 
49 int main()
50 {
51     freopen ("star.in","r",stdin);
52     freopen ("star.out","w",stdout);
53     int n,m,k;
54     scanf("%d%d%d%d",&n,&mod,&m,&k);
55     for (int i=1;i<=n;i++)
56     {
57         st[i].father=i;
58     }
59     int a,b,p;
60     for (int i=1;i<=m;i++)
61     {
62         scanf("%d%d%d",&a,&b,&p);
63         if (get(a)!=get(b))
64         {
65             marry(a,b,p);
66         }
67     }
68     for (int i=1;i<=k;i++)
69     {
70         scanf("%d%d",&a,&b);
71         if (get(a)!=get(b))
72         {
73             printf("Unknown\n");
74         }
75         else
76         {
77             if (st[a].len%mod==st[b].len%mod) printf("Yes\n");
78             else printf("No\n");
79         }
80     }
81     return 0;
82 }