SDUT 1488 数据结构实验：连通分量个数

数据结构实验：连通分量个数

Time Limit: 1000MS Memory Limit: 65536KB

Submit Statistic

Problem Description

在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，

否则，称该图为非连通图，则其中的极大连通子图称为连通分量，这里所谓的极大是指子图中包含的顶点个数极大。

例如：一个无向图有5个顶点，1-3-5是连通的，2是连通的，4是连通的，则这个无向图有3个连通分量。

Input

第一行是一个整数T，表示有T组测试样例(0 < T <= 50)。每个测试样例开始一行包括两个整数N，M，(0 < N <= 20,0 <= M <= 200)

分别代表N个顶点，和M条边。下面的M行，每行有两个整数u，v，顶点u和顶点v相连。

Output

每行一个整数，连通分量个数。

Example Input

Example Output

2
1

DQE:

本题水，建立图后对图顶点依次进行深度优先搜索，每个顶点开始前判断是否被访问过，若未被访问则为一个新的连通分量起点。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 #define MVN 110
 6 
 7 typedef struct AdjMatrix
 8 {
 9     int w;
10     char *info;
11 }AM;
12 
13 typedef struct MGraph
14 {
15     int vex[MVN];
16     AM arc[MVN][MVN];
17     int vexn,arcn;
18 }MG;
19 
20 void creat(MG &G)
21 {
22     int i,j,k;
23     for(i=1;i<=G.vexn;i++)
24         for(j=1;j<=G.vexn;j++)
25             G.arc[i][j].w=0;
26     for(k=1;k<=G.arcn;k++)
27     {
28         scanf("%d %d",&i,&j);
29         G.arc[i][j].w=G.arc[j][i].w=1;
30     }
31 }
32 
33 void DFS(MG &G,bool *f,int i)
34 {
35     f[i]=true;
36     int k;
37     for(k=1;k<=G.vexn;k++)
38         if(G.arc[i][k].w==1&&f[k]==false)
39             DFS(G,f,k);
40 }
41 
42 int main()
43 {
44     int t;
45     scanf("%d",&t);
46     while(t--)
47     {
48         MG G;
49         scanf("%d %d",&G.vexn,&G.arcn);
50         creat(G);
51         bool visited[MVN]={false};
52         int k,count=0;
53         for(k=1;k<=G.vexn;k++)
54             if(!visited[k])
55             {
56                 count++;
57                 DFS(G,visited,k);
58             }
59         printf("%d
",count);
60     }
61     return 0;
62 }
63 
64 /***************************************************
65 User name: ***
66 Result: Accepted
67 Take time: 0ms
68 Take Memory: 192KB
69 Submit time: 2016-11-18 20:16:28
70 ****************************************************/