如何判断无向图是否连通

---

任取两个顶点，我们都能找到一条路径从一点到达另一个点，这个图就是连通的

---

1.DFS法：

把一个图的所有顶点都进行一次DFS，当然，进行DFS的前提必须是这个点没有被遍历过。所以如果一个图是连通的，那么从一个点开始DFS，所有的点都会被遍历到，这样其他4个顶点就不用再DFS了。按照这个思路，定义一个count为DFS过顶点的个数，如果count=1，则图为连通的，否则就是不连通的。

测试数据：

5 3
0 1
0 2
2 3

示例代码：

bool occupy[N]={false};
void DFS(vector<vector<Node>>&v,int start){
  vector<int>q;
  int i;
  q.push_back(start);
  occupy[start]=true;
  while(!q.empty()){
    int t=q.front();
    q.pop_back();
    occupy[t]=true;
    for(i=0;i<v[t].size();i++){
      if(occupy[v[t][i].num]==false){
        q.push_back(v[t][i].num);
      }
    }
  }
}
void check_connection(vector<vector<Node>>&v){
  int i,counts=0;
  for(i=0;i<points;i++){
    if(occupy[i]==false){
        DFS(v,i);
        counts++;
    }
  }
  cout<<"counts:"<<counts<<endl;
}

---

2. 交并集

int fathers[N]={0};
int points,edges;
int findfather(int num){
  int f=num;
  while(fathers[f]!=f){
    f=fathers[f];
  }
  int p=f;
  f=num;
  int t;
  while(fathers[f]!=f){
    t=fathers[f];
    fathers[f]=p;
    f=t;
  }
  return f;
}
void merge(int a,int b){
  int a1=findfather(a);
  int b1=findfather(b);
  fathers[a1]=b1;
}
bool check_connection(){
  int i;
  for(i=1;i<points;i++){
    if(findfather(i)!=findfather(i-1)){
      return false;
    }
  }
  return true;
}