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

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


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

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

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

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

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

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

#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;}