poj2258 简单dfs The Settlers of Catan

dfs 边是双向的节点可以走多次开个二维数组标记边因为可以从任一节点出发所以n次dfs

View Code

 1 #include <stdio.h>
 2 #include<string.h>
 3 int x[26][26],v,w,n;
 4 void dfs(int i,int v)
 5 {
 6     int j;
 7     for(j = 0 ; j <= n-1 ; j++)
 8     {
 9         if(x[i][j] == 1)
10         {
11             x[i][j] = 0;
12             x[j][i] = 0;
13             dfs(j,v+1);
14             x[i][j] = 1;
15             x[j][i] = 1;
16         }
17     }
18     if(w<v)
19     w = v;
20 }
21 int main()
22 {
23     int m, i,j,a,b;
24     while(scanf("%d%d", &n, &m)!=EOF)
25     {
26         if(n == 0 && m == 0)
27         break;
28         memset(x,0,sizeof(x));
29         w = 0;
30         for(i = 1 ; i <= m ; i++)
31         {
32             scanf("%d%d", &a, &b);
33             x[a][b] = 1;
34             x[b][a] = 1;
35         }
36         for(i = 0 ; i <= n-1 ; i++)
37         {
38             dfs(i,0);
39         }
40         printf("%d\n", w);
41     }
42     return 0;
43 }