附代码
View Code
1 /* 2 无向图的联通分量 3 dfs 4 */ 5 #include<stdio.h> 6 #include<string.h> 7 const int maxn =30 ; 8 int map[ maxn ][ maxn ]; 9 int vis[ maxn ]; 10 int max; 11 void dfs( int now ){ 12 //vis[ now ]=1; 13 for( int i=1;i<=max;i++ ){ 14 if( map[ now ][ i ]==0||map[ i ][ now ]==0 ) continue; 15 if( vis[ i ]==1 ) continue; 16 vis[ i ]=1; 17 dfs( i ); 18 } 19 return ; 20 } 21 22 int main(){ 23 int T; 24 scanf("%d",&T); 25 getchar(); 26 while( T-- ){ 27 int edge; 28 char ch1,ch2; 29 char ss[ 5 ]; 30 scanf("%c %d",&ch1,&edge); 31 //getchar(); 32 //printf("max:%c edge:%d\n",ch1,edge); 33 max=ch1-'A'+1; 34 memset( map,0,sizeof(map) ); 35 for( int i=0;i<maxn;i++ ) map[ i ][ i ]=1; 36 memset( vis,0,sizeof(vis) ); 37 while( edge-- ){ 38 scanf("%s",ss); 39 ch1=ss[0],ch2=ss[1]; 40 //scanf("%c%c",&ch1,&ch2); 41 //getchar(); 42 //printf("%c%c\n",ch1,ch2); 43 map[ ch1-'A'+1 ][ ch2-'A'+1 ]=map[ ch2-'A'+1 ][ ch1-'A'+1 ]=1; 44 } 45 getchar(); 46 int ans=0; 47 for( int i=1;i<=max;i++ ){ 48 if( vis[ i ]==1 ) continue; 49 dfs( i ); 50 ans++; 51 } 52 printf("%d\n",ans); 53 } 54 return 0; 55 }