# Untitled

unknown
plain_text
2 years ago
3.4 kB
5
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;

int main()
{
// 8 nodes surrounding the cur node
int a[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int b[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int n, m;                  // total columns and rows of the matrix
int i, j;                  // iterators
int x, y;                  // indicate the pos. of a node
int ct;                    // counter
int **graph;               // store values of the input matrix
bool **visited;            // check if a node is visited
queue<vector<int>> q;      // queue for dfs
vector<int> cur;           // current node
map<int, vector<int>> res; // store the results

cin >> n >> m;

graph = new int *[m];
visited = new bool *[m];

for (i = 0; i < m; i++)
{
graph[i] = new int[n];
visited[i] = new bool[n];

for (j = 0; j < n; j++)
{
cin >> graph[i][j];

if (res.find(graph[i][j]) == res.end())
{
vector<int> temp;
res[graph[i][j]] = temp;
}

visited[i][j] = false;
}
}

// traverse throught each node in graph
for (i = 0; i < n * m; i++)
{
x = i % n;
y = (i - x) / n;

// skip if the node is visited
if (visited[y][x])
{
continue;
}

// count the total connected nodes
ct = 0;

// set up the starting node
if (i != 0)
{
cur.pop_back();
cur.pop_back();
}

cur.push_back(x);
cur.push_back(y);

q.push(cur);

while (!q.empty())
{
// get the cur node
cur = q.front();
q.pop();

x = cur.at(0);
y = cur.at(1);

// skip visited node
if (visited[y][x])
{
continue;
}

visited[y][x] = true; // set the cur node to visited
ct++;                 // increase the counter

// find all the connnected nodes w/ cur node
for (j = 0; j < 8; j++)
{
int adjX = x + a[j];
int adjY = y + b[j];

// skip the visited/invalid ones
{
continue;
}

// else add the connected node to queue
cur.pop_back();
cur.pop_back();

q.push(cur);
}
}

// add the result to the result map
res.find(graph[y][x])->second.push_back(ct);
}

// print the result
for (map<int, vector<int>>::iterator itr = res.begin(); itr != res.end(); ++itr)
{
cout << itr->first << " :";

sort(itr->second.begin(), itr->second.end()); // sort the vector
for (i = 0; i < itr->second.size(); i++)
{
cout << " " << itr->second.at(i);
}

cout << "\n";
}
}```