Problem Address：http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1404
简单的求连通量。连通量减1即为答案。
之前一直用的是DFS，所以今天试了一下BFS。
用一个queue的数组作为队列完成。
一次AC。
代码如下：
#include <iostream>using namespace std;int n;bool map[105][105];bool visited[105];void bfs(int v){ int queue[105]; int qs=0, qt=1; int i; queue[0] = v; while(qs!=qt)//如果队列不为空则继续搜索 { v = queue[qs]; qs++; for (i=1; i<=n; i++) { if (map[v][i]) { if (!visited[i])//搜到一个点把它放入队列 { visited[i] = true; queue[qt] = i; qt++; } } } }}int main(){ int m,i,j,a,b,ct; while(scanf("%d %d", &n, &m)!=EOF) { for (i=1; i<=n; i++) for (j=1; j<=n; j++) map[i][j] = false; for (i=1; i<=n; i++) visited[i] = false; for (i=0; i<m; i++) { scanf("%d %d", &a, &b); map[a][b] = true; map[b][a] = true; } ct = 0; for (i=1; i<=n; i++) { if (!visited[i]) { ct++; bfs(i); } } printf("%d/n", ct-1); } return 0;}
p.s.本来今天要去混别人的校赛，结果别人设了private，所以没办法进去%>_<%。继续好好做题好好努力！
