Intercommunication System Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte Total Submit: 23 Accepted: 12 Description 2010年是xx国一个多灾多难的一年，灾难使该国的通讯系统遭到了重创，全国共有n个通讯站点，分别从0到n-1进行编号，通讯部门对每两个站点的线路进行了检测，现在要你确定有哪些站点是彼此连通的。 Input 输入数据有多组，每组数据的第一行包含两个整数n和m，其中n为通讯站点个数，接下来有m行，每一行有2个整数a和b，表示站点a和b通讯正常。其中1<=n<=250。 Output 针对每组输入，将所有连通的站点进行分组，并将每组按照站点从小到大的顺序输出，如果有多组，所有的组根据每组最小的站点编号进行从小到大的排序后输出。 Sample Input
3 30 11 20 25 10 2
Sample Output
0 1 20 2134 |
#include#include #include #include #include using namespace std;const int maxn = 260;int n, m;int f[maxn];vector res[maxn];int getfather(int x) { if(f[x] == x) return x; return f[x] = getfather(f[x]);}void Merge(int a, int b) { int v1 = getfather(a); int v2 = getfather(b); if(v1 != v2) { if(v1 > v2) { f[v1] = v2; } else { f[v2] = v1; } }}void init() { int i; for(i = 0; i < n; i++) { res[i].clear(); } for(i = 0; i < n; i++) { f[i] = i; }}void work() { int parent; int i, j; for( i = 0; i < n; i++) { parent = getfather(i); res[parent].push_back(i); } for( i = 0; i < n; i++) { if(res[i].begin() != res[i].end()) sort(res[i].begin(), res[i].end()); } for( i = 0; i < n; i++) { if(res[i].size() == 0) continue; if(res[i].size() >= 2) { for( j = 0; j < (int)(res[i].size()-1); j++) { printf("%d ", res[i][j]); } printf("%d\n", res[i][j]); } else { printf("%d\n", res[i][0]); } } cout << endl;}int main(){ int from, to; while(scanf("%d%d", &n, &m) != EOF) { init(); for(int i = 0; i < m; i++) { scanf("%d%d", &from, &to); Merge(from, to); } work(); } return 0;}