codeforces 501C. Misha and Forest 解题报告

题目链接：http://codeforces.com/problemset/problem/501/C

题目意思：有 n 个点，编号为 0 ～ n-1。给出 n 个点的度数（即有多少个点跟它有边相连）以及跟它相连的点的编号的异或结果。最后需要输出整幅图的所有边的情况。

　　这道题确实是一道很好的题目！！！！它说拓扑排序的变形，需要队列的运用，还有就是异或计算的性质！！！（非一般厉害）

　　由于是无向无环的简单图，换言之就是一棵树啦^_^。那么它就肯定有叶子结点，叶子节点的度数为1，此时它相邻点的异或结果实际上就是所求点的编号了。然后把跟叶子节点相邻的点的度数-1，代表把叶子节点去除，此时异或结果是有变的。需要用本来的异或结果跟该叶子节点再异或一次，就得出除了这个叶子节点外其他点的异或值了。举个例子吧，假如有一幅图是这样的。

0 的相邻点有1、 2、 3，异或出来的结果是0，它的度数是3.那么当处理0-1这条边时，容易知道去除1这个点后，只有2和3异或了：10 ^ 11 = 1，刚好等于 1 ^ 2 ^ 3 ^ 1 （01 ^ 10 ^ 11 ^ 01）。异或的一个性质就是a^b^c^a = b ^ c。是不是很神奇呢～～～～当然我们总是处理那些度数为1的点，把这些点放入队列里面，依次处理。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <queue>

 using namespace std;

 #define f first

 #define s second

 const int maxn = (<<) + ;

 int degree[maxn], XOR_sum[maxn];

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     int n;

     while (scanf("%d", &n) != EOF) {

         queue<int> q;

         pair<int, int> ans[maxn];

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

             scanf("%d%d", &degree[i], &XOR_sum[i]);

             if (degree[i] == )

                 q.push(i);

         }

         int cnt = ;

         while (!q.empty()) {

             int from = q.front();

             q.pop();

             if (degree[from] == ) {   // 这句判断很重要，因为有可能degree[]--过程中使得变为0

                 int to = XOR_sum[from];

                 ans[cnt].f = from;

                 ans[cnt++].s = to;

                 degree[to]--;

                 XOR_sum[to] ^= from;   // 异或性质

                 if (degree[to] == )

                     q.push(to);

             }

         }

         printf("%d\n", cnt);

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

             printf("%d %d\n", ans[i].f, ans[i].s);

     }

     return ;

 }

巴特西

codeforces 501C. Misha and Forest 解题报告

最新文章

热门文章