# PM2C editorial

### PROBLEM LINK:

Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah

EASY

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);
}
}
}
``````
//