병렬 검사 집합
16356 단어 CPlusPlus
총결산 class UnionFind
{
public:
vector<int> father;
UnionFind(int num)//num
{
father.push_back(num);
}
int Find(int n)
{
//
while(father[n] != n)
{
n = father[n];
}
return n;
//
if(father[n] == n)
return n;
father[n] = Find(father[n]);//
return Find(father[n]);
}
void Union(int a, int b)
{
int fa = Find(a);
int fb = Find(b);
father[fb] = fa;
}
}
leetcode 547
leetcode 695
제목: 0과 1을 포함하는 비공 2차원 그룹grid를 지정합니다. 섬은 네 방향(수평 또는 수직)의 1(토지를 대표)으로 구성된 조합입니다.너는 2차원 행렬의 네 가장자리가 모두 물에 둘러싸여 있다고 가정할 수 있다.
주어진 2차원 그룹 중 가장 큰 섬 면적을 찾아라.(섬이 없으면 면적은 0으로 돌아갑니다.)#include
using namespace std;
int getArea(vector<vector<int> >& grid, int i, int j)
{
// +1 ,
if (i == grid.size() || i < 0)
return 0;
else if (j == grid[0].size() || j < 0)
return 0; ;
if (grid[i][j] == 1)
{
grid[i][j] = 0;
return 1 + getArea(grid, i + 1, j) + getArea(grid, i - 1, j ) + getArea(grid, i, j + 1) + getArea(grid, i, j - 1);
}
return 0;
};
int maxAreaOfIsland(vector<vector<int> >& grid)
{
int maxArea = 0;
int area = 0;
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[0].size(); j++)
{
if (grid[i][j] == 1)
{
// ,
area = getArea(grid, i, j);
maxArea = maxArea > area ? maxArea : area;
}
}
}
return maxArea;
};
int main()
{
int m,n;
scanf("%d,%d", &m, &n);
vector<vector<int> >nums(m,vector<int>(n,0));
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
{
int x;
scanf("%d,", &x);
nums[i][j] = x;
}
// for(int i = 0; i < m; i++)
// for(int j = 0; j < n; j++)
// {
// printf("%d",nums[i][j]);
// }
int ans = maxAreaOfIsland(nums);
printf("%d", ans);
return 0;
}
class UnionFind
{
public:
vector<int> father;
UnionFind(int num)//num
{
father.push_back(num);
}
int Find(int n)
{
//
while(father[n] != n)
{
n = father[n];
}
return n;
//
if(father[n] == n)
return n;
father[n] = Find(father[n]);//
return Find(father[n]);
}
void Union(int a, int b)
{
int fa = Find(a);
int fb = Find(b);
father[fb] = fa;
}
}
#include
using namespace std;
int getArea(vector<vector<int> >& grid, int i, int j)
{
// +1 ,
if (i == grid.size() || i < 0)
return 0;
else if (j == grid[0].size() || j < 0)
return 0; ;
if (grid[i][j] == 1)
{
grid[i][j] = 0;
return 1 + getArea(grid, i + 1, j) + getArea(grid, i - 1, j ) + getArea(grid, i, j + 1) + getArea(grid, i, j - 1);
}
return 0;
};
int maxAreaOfIsland(vector<vector<int> >& grid)
{
int maxArea = 0;
int area = 0;
for (int i = 0; i < grid.size(); i++)
{
for (int j = 0; j < grid[0].size(); j++)
{
if (grid[i][j] == 1)
{
// ,
area = getArea(grid, i, j);
maxArea = maxArea > area ? maxArea : area;
}
}
}
return maxArea;
};
int main()
{
int m,n;
scanf("%d,%d", &m, &n);
vector<vector<int> >nums(m,vector<int>(n,0));
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
{
int x;
scanf("%d,", &x);
nums[i][j] = x;
}
// for(int i = 0; i < m; i++)
// for(int j = 0; j < n; j++)
// {
// printf("%d",nums[i][j]);
// }
int ans = maxAreaOfIsland(nums);
printf("%d", ans);
return 0;
}