QM22A Editorial

PROBLEM LINK:

Practice
Contest

Author: Chandan Boruah
Tester: Harsh Raj
Editorialist: Chandan Boruah

DIFFICULTY:

EASY

PREREQUISITES:

Graph Theory, Brute Force

PROBLEM:

Given a graph on which a floyd warshal algorithm has been run, print the number of connected components in the graph.

QUICK EXPLANATION:

Build a list of lists, lets name it say LL. Iterate over the nodes of the graph, and for every node, interate over all lists in LL. Whenever, we find that a node is present in a list LL, we then add that node to that list in LL. In the end we print the number of lists in LL.

EXPLANATION:

Since, the connected components will have no paths between each other, so there would be no path between two components. So if we iterate over the nodes in the graph and we add the nodes to a list of lists and for every node we add the nodes in such a manner that we add the node to a new list if its not connected to any existing component, we can find all the connected components. Check Quick Explanation above for the implementation.

ALTERNATE EXPLANATION:

A graph traversal can also be used.

SOLUTIONS:

chandubaba's Solution
using System;
using System.Collections.Generic;
class some
{
	public static void Main()
	{
		int n=int.Parse(Console.ReadLine());
		int[,]arr=new int[n,n];
		for(int i=0;i<n;i++)
		{
			string[]ss=Console.ReadLine().Split();
			for(int j=0;j<n;j++)
			{
				arr[i,j]=int.Parse(ss[j]);
			}
		}
		
		List<List<int>>ll=new List<List<int>>();
		for(int i=0;i<n;i++)
		{
			List<int>range=new List<int>();
			range.Add(i);
			for(int j=0;j<n;j++)
			{
				if(i==j)continue;
				if(arr[i,j]==1)
				{
					range.Add(j);
				}
			}
			bool b=false;
			for(int j=0;j<ll.Count;j++)
			{
				
				foreach(int ii in ll[j])
				{
					if(range.Contains(ii))
					{
						b=true;break;
					}
				}
				if(b)
				{
					ll[j].AddRange(range);break;
				}
			}
			if(!b)ll.Add(range);
		}
		Console.WriteLine(ll.Count);
	}
}		
HarshRaj22's Solution
#include<bits/stdc++.h>
using namespace std;

#define ll long long int

const int N = 51;

vector<int> graph[N], vis(N,0);
int comp = 0;

void dfs(int node,int par=-1){
	vis[node] = 1;
	for(auto it:graph[node]){
	    if(vis[it])
	        continue;
	    dfs(it,node);
	}
}

int main(){
	int n;  
	cin >> n;

	for(int i=0;i<n;i++){
	    for(int j=0;j<n;j++){
	        int var;
	        cin >> var;
	        if(var){
	            graph[i].push_back(j);
	            graph[j].push_back(i);
	        }
	    }
	}

	for(int i=0;i<n;i++){
	    if(vis[i] == false){
	        dfs(i);
	        comp += 1;
	    }
	}

	cout << comp << '\n';
	return 0;
}