Решение задачи №141 «Дерево» с ACMP

Условие задачи

Неориентированный граф без петель и кратных ребер задан матрицей смежности. Требуется определить, является ли этот граф деревом.

Входные данные

Во входном файле INPUT.TXT записано сначала число N - количество вершин графа (от 1 до 100). Далее записана матрица смежности размером N×N, в которой 1 обозначает наличие ребра, 0 - его отсутствие. Матрица симметрична относительно главной диагонали.

Выходные данные

В выходной файл OUTPUT.TXT выведите сообщение YES, если граф является деревом, и NO в противном случае.

Решение на C++


    #include<iostream> 

using namespace std; 

int a[100][100],b[100],p[100],k,n; 

bool f=true;

void dfs(int j){

	b[j]=1;k++;

	for(int i=0;f&&i<n;++i) 

		if(a[j][i])

			if(!b[i]){p[i]=j;dfs(i);} 

				else if(p[j]!=i)f=false;}

int main(){ 

	int i,j;cin>>n; 

	for(i=0;i<n;++i) 

//----------------

#include<iostream>

#include<queue>

using namespace std;

int main() {

	int n,i,j,k,x1,y1,x2,y2,u,v;queue<pair<int,int>>q;

	int x[8]={-2,-2,-1,-1,1,1,2,2},

		y[8]={-1,1,-2,2,-2,2,-1,1};

	cin>>n;int d[n+1][n+1];

	for(i=0;i<=n;++i)

		for(j=0;j<=n;++j)d[i][j]=1000000000;

	cin>>x1>>y1>>x2>>y2;

	d[x1][y1]=0; q.push(make_pair(x1,y1));

	while(!q.empty()){

		i=q.front().first;j=q.front().second;q.pop();

		for(k=0;k<8;++k){u=i+x[k];v=j+y[k];

			if(u>0&&u<=n&&v>0&&v<=n&&d[u][v]>d[i][j]+1){

			d[u][v]=d[i][j]+1;q.push(make_pair(u,v));}}}

	cout<<d[x2][y2];

	return 0;}

	for(j=0;j<n;++j) 

		cin>>a[i][j]; 

	dfs(0);

	if(f&&k==n)cout<<"YES";

	else cout<<"NO"; 

return 0;}

Условия задач взяты с сайта acmp.ru