|
#include <iostream>
#include <queue>
using namespace std;
int connection1[4][4] = {{1,0,1,1},{0,1,0,0},{1,0,1,1},{1,0,1,1}};
int connection2[4][4] = {{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}};
//深度优先
void dfs(int array[4][4], int *flag, int pos)
{
? ? for (int i = 0; i < 4; i++)
? ? {
? ? ? ? if (array[pos][i] == 1 && *(flag + i) == 0)
? ? ? ? {
? ? ? ? ? ? *(flag + i) = 1;
? ? ? ? }
? ? }
}
int countObjects1(int array[4][4])
{
? ? int flag[4] = {0};
? ? int num = 0;
? ? for (int i = 0; i < 4; i++)
? ? {
? ? ? ? if (flag[i] == 0)
? ? ? ? {
? ? ? ? ? ? dfs(array, flag, i);
? ? ? ? ? ? num++;
? ? ? ? }
? ? }
? ??
? ? return num;
}
//广度优先
void bfs(int array[4][4], int *flag, int pos)
{
? ? queue<int> q;
? ? q.push(pos);
? ? while(!q.empty())
? ? {
? ? ? ? int tmp = q.front();
? ? ? ? q.pop();
? ? ? ? *(flag + tmp) = 1;
? ? ? ? for (int i = 0; i < 4; i++)
? ? ? ? {
? ? ? ? ? ? if (*(flag + i) == 0 && array[tmp][i] == 1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? q.push(i);
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
int countObjects2(int array[4][4])
{
? ? int flag[4] = {0};
? ? int num = 0;
? ? for (int i = 0; i < 4; i++)
? ? {
? ? ? ? if (flag[i] == 0)
? ? ? ? {
? ? ? ? ? ? bfs(array, flag, i);
? ? ? ? ? ? num++;
? ? ? ? }
? ? }
? ??
? ? return num;
}
//并查集
int find(int *flag, int pos)
{
? ? if (flag[pos] == pos)
? ? {
? ? ? ? return pos;
? ? }
? ??
? ? flag[pos] = find(flag, flag[pos]);
? ? return flag[pos];
}
void link(int array[4][4], int *flag, int *level, int pos1, int pos2)
{
? ? int p1 = find(flag, pos1);
? ? int p2 = find(flag, pos2);
? ??
? ? if (p1 == p2)
? ? {
? ? ? ? return;
? ? }
? ??
? ? if (level[p1] > level[p2])
? ? {
? ? ? ? flag[p2] = p1;
? ? }
? ? else if (level[p1] < level[p2])
? ? {
? ? ? ? flag[p1] = p2;
? ? }
? ? else
? ? {
? ? ? ? flag[p1] = p2;
? ? ? ? level[p2] += 1;
? ? }
? ??
? ? return;
}
int countObjects3(int array[4][4])
{
? ? int level[4] = {0};
? ? int flag[4] = {0};
? ? for (int i = 0; i < 4; i++)
? ? {
? ? ? ? flag[i] = i;
? ? ? ? level[i] = 1;
? ? }
? ? ? ??
? ? for (int i = 0; i < 4; i++)
? ? ? ? for (int j = i; j < 4; j++)
? ? ? ? {
? ? ? ? ? ? if (array[i][j] == 1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? link(array, flag, level, i, j);
? ? ? ? ? ? }
? ? ? ? }
? ??
? ? int num = 0;
? ? for (int i = 0; i < 4; i++)
? ? {
? ? ? ? if (i == flag[i])
? ? ? ? ? ? num++;
? ? }
? ??
? ? return num;
}
int main() {
?? ?cout ?<< countObjects1(connection1) << endl;
?? ?cout ?<< countObjects1(connection2) << endl;
?? ?
?? ?cout ?<< countObjects2(connection1) << endl;
?? ?cout ?<< countObjects2(connection2) << endl;
?? ?
?? ?cout ?<< countObjects3(connection1) << endl;
?? ?cout ?<< countObjects3(connection2) << endl;
?? ?
?? ?return 0;
}
|