ĐỀ 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 (27)
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 (15.65 KB, 3 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è 27
Trong Bé §Ò ¤n TËp
#include<iostream.h>
#include<conio.h>
#include<fstream.h>
ifstream Tepvao("C:/cau truc du lieu/dethi/mang27.in.txt");
ofstream Tepra("C:/cau truc du lieu/dethi/kequa27.out.txt");
int n,a[100][100];
void NhapDL(int &n,int a[][100])
{
int k;
Tepvao>>n>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
Tepvao>>a[i][j];
}
int dem=0,x[100];
void DFS(int i)
{
x[i]=1;
for(int j=1;j<=n;j++)
if(x[j]==0&&a[i][j]==1)DFS(j);
}
void DFS(int i,int a[][100],int n,int k)
{
x[i]=1;
for(int j=1;j<=n;j++)
if(x[j]==0&&a[i][j]!=0)
{
if(j==k)
{
dem=1;
return ;
}
DFS(j,a,n,k);
}
}
int Cat()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
dem=0;
if(a[i][j]!=0)
{
a[i][j]=0;
for(int m=1;m<=n;m++)
x[m]=0;
DFS(i,a,n,j);
if(dem==1)
{
for(int m=1;m<=n;m++)
x[m]=0;
DFS(1);
int k=1;
for(int m=1;m<=n;m++)
if(x[m]==0){k=0;break;}
if(k==0) a[i][j]=1;
}
else a[i][j]=1;
for(int m=1;m<=n;m++)
x[m]=0;
DFS(1);
for(int m=1;m<=n;m++)
if(x[m]==0)
{
a[i][j]=1;
break;
}
}
}
int hj=0;
int aa[100],bb[100];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i][j]>0&&j>i){hj++;
aa[hj]=i;
bb[hj]=j;
}
Tepra<<n<<" "<<hj<<endl;
for(int i=1;i<=hj;i++)
Tepra<<aa[i]<<" "<<bb[i]<<endl;
}
main()
{
NhapDL(n,a);
Cat();
}
