Problem Description
求解無向圖的各連通分支
輸入：
第一行為圖的節(jié)點(diǎn)數(shù)n（節(jié)點(diǎn)編號(hào)0至n-1，0<n<=10）
從第二行開始列出圖的邊功偿，-1表示輸入結(jié)束
輸出：
輸出每個(gè)連通分支的廣度優(yōu)先搜索序列（從連通分支的最小編號(hào)開始），不同分支以最小編號(hào)遞增順序列出
測試輸入
8
0 5
5 2
4 5
5 6
6 2
3 7
0 2
-1
測試輸出
0-5-2-4-6
1
3-7
AcCode
//
// main.cpp
// 無向圖的各連通分支
//
// Created by jetviper on 2017/3/26.
// Copyright ? 2017年 jetviper. All rights reserved.
//
#include <stdio.h>
int n;
struct{
int vsd;
int bnum;
int linkto[18];
}node[18];
void bfs(int now){
int count=0,temp[18];
if(node[now].vsd==0){
node[now].vsd=1;
printf("%d",now);
}
for(int i=0;i<node[now].bnum;i++) {
for(int j=i;j<node[now].bnum;j++){
if(node[now].linkto[i]>node[now].linkto[j]){
int tmp = node[now].linkto[i];
node[now].linkto[i] = node[now].linkto[j];
node[now].linkto[j] = tmp;
}
}
}
for(int i=0;i<node[now].bnum;i++) {
if(node[node[now].linkto[i]].vsd==0) {
printf("-%d",node[now].linkto[i]);
node[node[now].linkto[i]].vsd = 1;
temp[count]=node[now].linkto[i];
count++;
}
}
for(int i=0;i<count;i++) {
bfs(temp[i]);
}
}
int main() {
int x,y;
scanf("%d",&n);
for(int i=0;i<n;i++){
node[i].vsd=0;
node[i].bnum=0;
}
while(1){
scanf("%d",&x);
if(x==-1)break;
scanf("%d",&y);
node[x].linkto[node[x].bnum]=y;
node[x].bnum++;
node[y].linkto[node[y].bnum]=x;
node[y].bnum++;
}
for(int i=0;i<n;i++) {
if(node[i].vsd==0) {
bfs(i);
printf("\n");
}
}
return 0;
}
