圖的深度遍歷 Time Limit: 1000MS Memory Limit: 65536KB PRoblem Description 請定一個無向圖，頂點(diǎn)編號從0到n-1，用深度優(yōu)先搜索(DFS)，遍歷并輸出。遍歷時，先遍歷節(jié)點(diǎn)編號小的。 Input 輸入第一行為整數(shù)n（0 < n < 100），表示數(shù)據(jù)的組數(shù)。 對于每組數(shù)據(jù)，第一行是兩個整數(shù)k,m（0 ＜ k ＜ 100，0 ＜ m ＜ k*k），表示有m條邊，k個頂點(diǎn)。 下面的m行，每行是空格隔開的兩個整數(shù)u，v，表示一條連接u，v頂點(diǎn)的無向邊。 Output 輸出有n行，對應(yīng)n組輸出，每行為用空格隔開的k個整數(shù)，對應(yīng)一組數(shù)據(jù)，表示DFS的遍歷結(jié)果。 Example Input
1 4 4 0 1 0 2 0 3 2 3
Example Output
0 1 2 3
#include<stdio.h>#include<string.h>int map[105][105];//圖int vis[105];//標(biāo)記該點(diǎn)是否已經(jīng)走到void dfs(int i, int k){ vis[i] = 1; if(i == 0) printf("%d", i); else printf(" %d", i); int j; for(j = 0; j < k; j++) { if(!vis[j] && map[i][j]) dfs(j, k);//i->j沒有走過 dfs一波 }}int main(){ int u, v; int k, m, n; while(~scanf("%d", &n)) { while(n--) { memset(map, 0, sizeof(map)); memset(vis, 0, sizeof(vis)); scanf("%d %d", &k, &m); while(m--) { scanf("%d %d", &u, &v); map[u][v] = 1;//題目沒有權(quán)值，就假設(shè)它為1 map[v][u] = 1; } if(!vis[0]) dfs(0, k); printf("/n"); } } return 0;}新聞熱點(diǎn)
疑難解答
