题记 这道题首先可以暴力搜索，读完之后一个个地dfs，这里就不赘述了。另一个思路就是并查集，其实也挺容易想到的，如果a,b两个植物的根不一样，那么就把b的总根挂在a的总根下面，最后遍历一遍找出来plant[i]==i的就是最后的大根，数出来就是答案了。
#include <iostream> using namespace std; const int Maxn=1e6; int plant[Maxn]; //寻根 int findBase(int x){ while(plant[x]!=x) x=plant[x]; return x; } int main() { int m,n,k; int a,b; int count=0; cin>>m>>n; cin>>k; for(int i=1;i<=m*n;i++)//初始化，一开始每个植物的根就是整体的根 plant[i]=i; for(int i=0;i<k;i++){ cin>>a>>b; if(findBase(a)!=findBase(b)) plant[findBase(b)]=plant[findBase(a)]; } for(int i=1;i<=m*n;i++){ if(plant[i]==i){ count++; } } cout<<count<<endl; return 0; }