分析
并查集问题,遍历所有边把点之间的关系关联起来,最后看一下总的连通块个数,减去1就是答案。
C++ 代码
class Solution {
public:
int find(int x)
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
unordered_set<int> s;
vector<int> fa;
int makeConnected(int n, vector<vector<int>>& connections) {
int need=connections.size();
if(need+1<n) return -1; //边数+1小于总点数,肯定不能构成强连通图
fa=vector<int>(n);
for(int i=0;i<n;i++) fa[i]=i;
for(int i=0;i<need;i++)
{
int faa=find(connections[i][0]),fbb=find(connections[i][1]);
fa[faa]=fbb;
}
for(int i=0;i<n;i++)
{
s.insert(find(fa[i])); //统计总连通块的个数
}
return s.size()-1; //返回总个数-1
}
};