QM12B - editorial

editorial
,
1

PROBLEM LINK:

Practice

Contest

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

DIFFICULTY:

MEDIUM

PREREQUISITES:

Graph Theory, Floyd Warshal.

PROBLEM:

Given a graph, find if there is a cycle from node 0 to itself.

QUICK EXPLANATION:

Run floyd Warshal on the graph and check for node 0.

EXPLANATION:

On running floyd warshal algorithm on a graph you can know if there is a path from one node to another. So after running the algorithm check for node 0. If its 1 then print YES else print NO.

AUTHOR’S AND TESTER’S SOLUTIONS:

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]);
			}
		}
		for(int k=0;k<n;k++)
		{
			for(int i=0;i<n;i++)
			{
				for(int j=0;j<n;j++)
				{
					if(arr[i,k]==1 && arr[k,j]==1)arr[i,j]=1;
				}
			}
		}
		if(arr[0,0]==1)Console.WriteLine("YES");
		else Console.WriteLine("NO");
	}
}