Skip to content

Instantly share code, notes, and snippets.

@hsnks100
Created March 8, 2016 23:52
Show Gist options
  • Save hsnks100/4ccab35372eea125be92 to your computer and use it in GitHub Desktop.
Save hsnks100/4ccab35372eea125be92 to your computer and use it in GitHub Desktop.
#include <iostream>
#include <algorithm>
#include <queue>
#include <functional>
#include <string>
#include <sstream>
using namespace std;
int n;
int graph[51][51];
queue<pair<int, int>> que;
int visit[51][51];
int numberingGraph[51][51];
void show(int (*g)[51], int t)
{
for(int i=1; i<=t; i++)
{
for(int j=1; j<=t; j++)
{
printf("%d ", g[i][j]);
}
printf("\n");
}
}
void bfs(int y, int x, int numbering)
{
que.push(make_pair(y, x));
visit[y][x] = 1;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
while(!que.empty())
{
auto q = que.front();
que.pop();
numberingGraph[
for(int i=0; i<=3; i++)
{
int newY = q.first + dy[i];
int newX = q.second + dx[i];
if(visit[newY][newX] == 0 && graph[newY][newX] == 1)
{
que.push(make_pair(newY, newX));
visit[newY][newX] = 1;
}
}
}
}
int main()
{
cin >> n;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
char t;
cin >> t;
graph[i][j] = t - '0';
}
}
show(graph, n);
int numbering = 0;
bfs(1, 1, ++numbering);
show(
return 0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(graph[i][j] == 1 && visit[i][j] == 0)
{
bfs(i, j, ++numbering);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment