ĐỀ THI MÔN Cấu Trúc Dữ Liệu và Giải Thuật học viện công nghệ bưu chính viễn thông (23)
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (17.86 KB, 4 trang )
M¹nh D¬ng Biªn So¹n
Bé M«n CÊu Tróc D÷ LiÖu
Gi¶i ThuËt 2012
§ª Sè 23
Trong Bé §Ò ¤n TËp
#include<iostream.h>
#include<fstream.h>
#include<math.h>
#include<conio.h>
#include<time.h>
#include<string.h>
#include<stdio.h>
ifstream datain("C:/cau truc du lieu/dethi/dske23.in.txt");
/*
Thuat toan kiem tra tinh lien thong cua do thi co huong
*/
char S[100][200],x[100];
void NhapDL(int &n)
{
datain>>n;
for(int i=0;i<=n;i++)
datain.getline(S[i],200,'\n');
}
int ket(char S)
{
int k=int (S)-int ('0');
return k;
}
int chuyen(char S[])
{int j=0,k=0;
for(int i=strlen(S)-1;i>=0;i )
{k+=ket(S[i])*pow(10,j);j++;}
return k;
}
void ChuyenKe(int a[][100],int n)
{
int dem=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=0;
for(int i=1;i<=n;i++)
{
int j=0;
while(S[i][j]!='\0')
{
if(S[i][j]>='0'&&S[i][j]<='9')
{
char SS[200];
int k=0;
while(S[i][j]>='0'&&S[i][j]<='9')
{
SS[k]=S[i][j];
k++;
j++;
}
SS[k]='\0';j++;
a[i][chuyen(SS)]=1;
}
}
}
}
void DFS(int i,int a[][100],int n)
{
x[i]=1;
for(int k=1;k<=n;k++)
if(x[k]==0&&a[i][k]==1)
DFS(k,a,n);
}
int dem=0;
void DFS(int i,int j,int a[][100],int n)
{
x[i]=1;
for(int k=1;k<=n;k++)
if(x[k]==0&&a[i][k]==1)
{
if(k==j){
dem=1;
return ;
}
DFS(k,j,a,n);
}
}
int LienTM(int a[][100],int n)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(j!=i)
{
for(int u=1;u<=n;u++)
x[u]=0;
dem=0;
DFS(i,j,a,n);
if(dem==0)return 0;
}
}
return 1;
}
int LienTY(int a[][100],int n)
{
for(int u=1;u<=n;u++)x[u]=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(a[i][j]==1)
a[j][i]=1;
DFS(1,a,n);
for(int i=1;i<=n;i++)
if(x[i]==0)return 0;
return 1;
}
main()
{
int n;
NhapDL(n);
int a[100][100];
ChuyenKe(a,n);
if(LienTM(a,n)==1)cout<<"Do thi lien thong manh"<<endl;
else if(LienTY(a,n)==1)cout<<"Do thi lien thong yeu"<<endl;
else cout<<"Do thi khong lien thong manh, khong lien thong yeu"<<endl;
}
