codevs2597团伙

 1 #include<stdio.h>
 2 #include<string.h>
 3 int N,M;
 4 int a[1020][1020]={0};
 5 
 6 int  pre[1050];
 7 bool t[1050];  //t 用于标记独立块的根结点
 8 
 9 int Find(int x);
10 void mix(int x,int y);
11 
12 int main(int argc, char *argv[])
13 {
14     int i,j,k,p,q;
15     char temp[100];
16     int ans=0;
17     freopen("data2.in","r",stdin);
18 
19     scanf("%d%d",&N,&M);getchar();
20     //printf("%d %d
",N,M);
21     for(i=1;i<=N;i++)//并查集的初始化,每一个节点一开始都是各自独立的
22         pre[i]=i;
23     for(i=0;i<M;i++)
24     {
25         scanf("%s %d %d",temp,&p,&q);getchar();
26         //printf("%c %d %d
",temp[0],p,q);
27         if(temp[0]==‘F‘)
28         {
29             a[p][q]=1; a[q][p]=1;
30         }
31         else if(temp[0]==‘E‘)
32         {
33             a[p][q]=2; a[q][p]=2;
34         }
35     }
36 
37     for(i=1;i<=N;i++)
38     {
39         for(j=1;j<=N;j++)
40         {
41             if(a[i][j]==2)
42             {
43                 for(k=1;k<=N;k++)
44                     if(a[j][k]==2) { a[i][k]=1; a[k][i]=1; }
45             }
46         }
47     }
48 
49     for(i=1;i<=N;i++)
50     {
51         for(j=1;j<=N;j++)
52         {
53             if(a[i][j]==1) mix(i,j);
54         }
55     }
56     memset(t,0,sizeof(t));
57     for(i=1;i<=N;i++)          //标记根结点（作为掌门（队长）的节点会被标记为1.比如编号i的节点做掌门，则t[i]=1）
58     {  t[Find(i)]=1;  }
59     for(ans=0,i=1;i<=N;i++)    //统计掌门（队长）的人数（就是队伍的数量）
60         if(t[i]) ans++;
61     printf("%ld
",ans);
62     return 0;
63 }
64 
65 int Find(int x)
66 {
67     int r=x;
68     while(r!=pre[r])
69         r=pre[r];
70 
71     int i=x,j;
72     while(pre[i]!=r)
73     {
74         j=pre[i];
75         pre[i]=r;
76         i=j;
77     }
78     return r;
79 }
80 void mix(int x,int y)
81 {
82     int fx=Find(x),fy=Find(y);
83     if(fx!=fy)
84     {
85         pre[fy]=fx;
86     }
87 }

    for(i=0;i<M;i++)
    {
        scanf("%s %d %d",temp,&p,&q);getchar();
        //printf("%c %d %d
",temp[0],p,q);
        if(temp[0]==‘F‘)
        {
            mix(p,q);
        }
        else if(temp[0]==‘E‘)
        {
            if(f[p]==0) f[p]=q;//记录p第一次遇到的敌人q
            else mix(q,f[p]);  //遇到p的其他敌人时，把新遇到的敌人q与最开始遇到的敌人f[q]设为朋友关系（因为这两人都是p的敌人，所以两人是朋友）
            if(f[q]==0) f[q]=p;//同样地，要记录q首次遇到的敌人
            else mix(p,f[q]);  //遇到q的其他敌人时，将新遇到的敌人与首次遇到的敌人f[p]设为朋友
        }
    }

 1 #include<stdio.h>
 2 #include<string.h>
 3 int N,M;
 4 int a[1020][1020]={0};
 5 int f[1020]={0};
 6 
 7 int  pre[1050];
 8 bool t[1050];  //t 用于标记独立块的根结点
 9 
10 int Find(int x);
11 void mix(int x,int y);
12 
13 int main(int argc, char *argv[])
14 {
15     int i,j,k,p,q;
16     char temp[100];
17     int ans=0;
18     freopen("data2.in","r",stdin);
19 
20     scanf("%d%d",&N,&M);getchar();
21     //printf("%d %d
",N,M);
22     for(i=1;i<=N;i++)//并查集的初始化,每一个节点一开始都是各自独立的
23         pre[i]=i;
24     for(i=0;i<M;i++)
25     {
26         scanf("%s %d %d",temp,&p,&q);getchar();
27         //printf("%c %d %d
",temp[0],p,q);
28         if(temp[0]==‘F‘)
29         {
30             mix(p,q);
31         }
32         else if(temp[0]==‘E‘)
33         {
34             if(f[p]==0) f[p]=q;
35             else mix(q,f[p]);
36             if(f[q]==0) f[q]=p;
37             else mix(p,f[q]);
38         }
39     }
40 
41     memset(t,0,sizeof(t));
42     for(i=1;i<=N;i++)          //标记根结点（作为掌门（队长）的节点会被标记为1.比如编号i的节点做掌门，则t[i]=1）
43     {
44         t[Find(i)]=1;
45     }
46     for(ans=0,i=1;i<=N;i++)    //统计掌门（队长）的人数（就是队伍的数量）
47         if(t[i]) ans++;
48     printf("%d
",ans);
49     return 0;
50 }
51 
52 int Find(int x)
53 {
54     int r=x;
55     while(r!=pre[r])
56         r=pre[r];
57 
58     int i=x,j;
59     while(pre[i]!=r)
60     {
61         j=pre[i];
62         pre[i]=r;
63         i=j;
64     }
65     return r;
66 }
67 void mix(int x,int y)
68 {
69     int fx=Find(x),fy=Find(y);
70     if(fx!=fy)
71     {
72         pre[fy]=fx;
73     }
74 }