05- 그림 1.List Components (25)
시간 제한
200 ms
메모리 제한
65536 kB
코드 길이 제한
8000 B
판정 절차
Standard
작자
CHEN, Yue
For a given undirected graph with N vertices and E edges, please list all the connected components by both DFS and BFS. Assume that all the vertices are numbered from 0 to N-1. While searching, assume that we always start from the vertex with the smallest index, and visit its adjacent vertices in ascending order of their indices.
Input Specification:
Each input file contains one test case. For each case, the first line gives two integers N (0
For each test case, print in each line a connected component in the format "{ v1 v2 ... vk }". First print the result obtained by DFS, then by BFS.
Sample Input:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
Sample Output:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
#include <stdio.h>
void DFS(int graph[][10], int *visited, int v, int n, int *ret) {
visited[v] = 1;
ret[++ret[0]] = v;
for (int i = 0; i < n; ++i) {
if (v != i && graph[v][i] && !visited[i]) {
DFS(graph, visited, i, n, ret);
}
}
}
void BFS(int graph[][10], int *visited, int v, int n) {
int queque[20] = {};
int head = 0, rear = 0;
queque[rear++] = v; //
visited[v] = 1;
printf("{ ");
while (rear > head) {
int curr = queque[head++]; //
printf("%d ", curr);
for (int i = 0; i < n; ++i) //
if (graph[curr][i] && !visited[i]) {
visited[i] = 1;
queque[rear++] = i;
}
}
printf("}
");
}
int main() {
// freopen("test.txt", "r", stdin);
int n, edge;
scanf("%d%d", &n, &edge);
int graph[10][10] = {};
for (int i = 0; i < edge; ++i) { //
int v1, v2;
scanf("%d%d", &v1, &v2);
graph[v1][v2] = 1;
graph[v2][v1] = 1;
}
int visited[10] = {};
for (int i = 0; i < n; ++i) {
int ret[11] = {}; //
if (!visited[i]) {
DFS(graph, visited, i, n, ret);
printf("{ ");
for (int j = 1; j <= ret[0]; ++j) {
printf("%d ", ret[j]);
}
printf("}
");
}
}
for (int i = 0; i < n; ++i) //
visited[i] = 0;
for (int i = 0; i < n; ++i) { //BFS
if (!visited[i]) {
BFS(graph, visited, i, n);
}
}
return 0;
}
제목 링크:http://www.patest.cn/contests/mooc-ds/05-%E5%9B%BE1좋은 웹페이지 즐겨찾기
