admin 管理员组

文章数量: 888297

阻击火箭队

小明很喜欢《神奇宝贝》（又叫做《宠物小精灵》）这部动漫，他几乎每天都要看一集神奇宝贝的动画。有一天他做了一个梦，梦见他也置身于神奇宝贝的世界，并且加入了主人公小智一行人的修行队伍。

这天，他们来到了一个由很多岛屿组成的城市。这座城市的神奇宝贝中心坐落在e岛上，里面有许多稀有的神奇宝贝。接下来正像每一集的动画那样，每次都华丽登场、悲剧收场的火箭队又出现了！
他们的目标是到e岛上抢夺神奇宝贝中心里的神奇宝贝，小明和小智他们决定阻止火箭队的行动。他们拿出该城市的地图，发现这些岛是由许多桥连接起来的。火箭队目前所在的岛是s岛，这次火箭队没有带任何高科技装备，所以他们只能从s岛走到e岛。小明和小智他们希望能找到火箭队一定会经过的桥，在那里阻止他们的行动。现在请你帮他们找出那些火箭队一定会经过的桥。

输入

输入包含多组测试数据。
每组输入的第一行为两个整数n和m（2<=n,m<=10），n表示岛的个数，m表示桥的个数。
接下来m行，每行输入两个整数a和b（0<=a,b<n），表示a岛和b岛由桥i相连接，i是桥的序号，i从0开始，按照输入的顺序依次增加1，直到m-1。
最后再输入一行，为两个整数s和e（0<=s,e<n），s表示火箭队目前所在的岛，e表示神奇宝贝中心所在的岛。
题目数据保证s岛和e岛是连通的。同时，任意两个岛之间可能会存在多个桥将它们直接相连。
相邻两组输入数据之间空一行。

输出

对于每组输入数据，找出火箭队一定会经过的桥。
每组首先在一行中输出火箭队一定会经过的桥的个数x，如果x不为0，则另起一行输出桥的序号，按照升序排序。如果x为0，则无需输出任何东西。

样例输入 

3 2
0 1
1 2
0 26 7
1 3
0 2
2 0
4 0
1 3
1 5
0 1
2 3

样例输出 

2
0 1
1
6

先存下m条边，然后构建m次并查集，每次漏掉一条边，当漏掉某条边时从s到e不再连通了，说明这条边是s到e必须经过的边，此时记录该边。s-e连通与否用并查集很容易实现，整体就是构建m次并查集就行了。很简单。

#include <iostream>
using namespace std;
int n, m, s, e, res, arr1[11], arr2[11], root[11], edge[11];
int getfather(int a)
{if (root[a] == a)return a;return root[a] = getfather(root[a]);
}
void _union(int a, int b)
{int fa = getfather(a);int fb = getfather(b);if (fa != fb)root[fa] = fb;
}
int main()
{while (cin >> n >> m){for (int i = 0; i < m; i++){cin >> arr1[i] >> arr2[i];}cin >> s >> e;res = 0;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){root[j] = j;   //并查集初始化}for (int j = 0; j < m; j++){if (j == i){continue;   //漏掉的一条边}_union(arr1[j], arr2[j]);   //并入集合}if (getfather(s) != getfather(e))   //判断从s到e是否连通edge[res++] = i;     //不连通了就说明这条边必须经过}cout << res << endl;for (int i = 0; i < res; i++)    //依次输出必须经过的边{cout << edge[i];if (i < res - 1)cout << " ";elsecout << endl;}}system("pause");return 0;
}

 

本文标签： 阻击火箭队

版权声明：本文标题：阻击火箭队 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1688273945h200149.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。