PROBLEM LINK:
Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah
DIFFICULTY:
EASY
PREREQUISITES:
Graph Traversal
PROBLEM:
Given a graph. Find number of contiguous areas in the graph.
QUICK EXPLANATION:
Do a graph traversal from every node, as root, of the graph. Whenever the node the node has already been traversed don’t increment the counter, else increment the counter. Print that counter.
EXPLANATION:
Make a nested for loop for the various rows and columns in the adjacency matrix for the graph provided. Enter the nodes in a linked list if it hasn’t been visited yet, increment counter whenever such a node is visited because it means its from a new area. Visit all the nodes that can be visited from that node.
AUTHOR’S SOLUTION IN C#:
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
int n=int.Parse(Console.ReadLine());
while((n--)>0)
{
string[]ss=Console.ReadLine().Split();
int a=int.Parse(ss[0]);
int b=int.Parse(ss[1]);
int[,]arr=new int[a,b];
for(int i=0;i<a;i++)
{
string[]t=Console.ReadLine().Split();
for(int j=0;j<b;j++)
{
arr[i,j]=int.Parse(t[j]+"");
}
}
Queue<int>ll=new Queue<int>();
List<string>done=new List<string>();
int[]dx={1,-1,0,0};
int[]dy={0,0,-1,1};
int count=0;
for(int i=0;i<a;i++)
{
for(int j=0;j<b;j++)
{
if(done.Contains(i+" "+j))continue;
count++;
ll.Enqueue(i);
ll.Enqueue(j);
done.Add(i+" "+j);
while(ll.Count>0)
{
int x=ll.Dequeue();
int y=ll.Dequeue();
for(int ii=0;ii<4;ii++)
{
int xx=dx[ii]+x;
int yy=dy[ii]+y;
if(xx>=0 && yy>=0 && xx<a && yy<b)
{
if(!done.Contains(xx+" "+yy))
{
if(arr[xx,yy]==arr[x,y])
{
done.Add(xx+" "+yy);
ll.Enqueue(xx);
ll.Enqueue(yy);
}
}
}
}
}
}
}Console.WriteLine(count);
}
}
}