LA 3027 合作网络

题意：

有n个结点，初始时每个结点的父节点都不存在。你的任务是执行一次I操作和E操作，格式如下：

I u v：把结点u的父节点设为v，距离为|u-v|除以1000的余数。输入保证执行指令前u没有父节点。

E u：询问u到根结点的距离。

思路：

主要思想是并查集，记录一下每个结点到根结点的距离即可。

 #include<iostream>

 #include<cstring>

 using namespace std;

 const int maxn =  + ;

 int p[maxn], d[maxn];

 int n;

 char c;

 int find(int x)

 {

     if (p[x] != x)

         return d[x] + find(p[x]);

     else

         return d[x];

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     int T;

     scanf("%d", &T);

     while (T--)

     {

         memset(d, , sizeof(d));

         scanf("%d", &n);

         for (int i = ; i <= n; i++)

             p[i] = i;

         int u, v;

         while (scanf("%c",&c) && c != 'O')

         {

             if (c == 'E')

             {

                 scanf("%d", &u);

                 int sum=find(u);

                 cout << sum << endl;

             }

             else if (c == 'I')

             {

                 scanf("%d%d", &u, &v);

                 p[u] = v;

                 d[u] = abs(v - u) % ;

             }

         }

     }

 }

巴特西

LA 3027 合作网络

最新文章

热门文章