UVa 11503 - Virtual Friends-白红宇

UVa 11503 - Virtual Friends

阅读量：6738 次

发布时间：2019-06-25

本文共 1518 字，大约阅读时间需要 5 分钟。

　　题目大意：给出若干对朋友关系，每给出一对朋友关系，就输出二者所在关系网中的人数。

　　首先是对每个人编号，使用map简化编号过程，然后就是使用并查集更新集合。要注意的是当给出Ａ和Ｂ的朋友关系时，无论Ａ和Ｂ在此之前是否是朋友（属于同一个集合），都要输出建立关系后的朋友网中的人数。

1 #include 
      
        2 #include 
       
         3 #include 
         4 #include 
         
           5 using namespace std; 6 #define MAXN 100000*2+100 7 typedef map
          
            msi; 8  9 int p_cnt;  // the number of people10 msi m;11 int p[MAXN], cnt[MAXN];  // cnt[i] save the number of nodes which root is i12 13 void add_node(string name)14 {15     if (!m.count(name))16     {17         m[name] = p_cnt;18         p[p_cnt] = p_cnt;19         cnt[p_cnt] = 1;20         p_cnt++;21     }22 }23 24 int find(int x)25 {26     return (x == p[x]) ? x : p[x] = find(p[x]);27 }28 29 int main()30 {31 #ifdef LOCAL32     freopen("in", "r", stdin);33 #endif34     int T;35     scanf("%d", &T);36     while (T--)37     {38         int n;39         scanf("%d", &n);40         getchar();41         string name1, name2;42         m.clear();43         p_cnt = 0;44         while (n--)45         {46             cin >> name1 >> name2;47             add_node(name1);48             add_node(name2);49             int pa = find(m[name1]);50             int pb = find(m[name2]);51             if (pa != pb)52             {53                 p[pb] = pa;54                 cnt[pa] += cnt[pb];55             }56             printf("%d\n", cnt[pa]);57         }58     }59     return 0;60 }

View Code

转载于:https://www.cnblogs.com/xiaobaibuhei/p/3294719.html

你可能感兴趣的文章