讨论 / 解法O(N^2)C++
xyz32768 2016-12-22 06:31:26
点我顶贴 收藏 删除
#include <cstring>

#include <iostream>

using namespace std;

int n,p,r[201][201],l[201];

bool g[201][201],b[201],lt[201];

void dfs(int i,int s)

{

int j;b[i]=1;

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

if(!b[j] && j!=s && g[i][j])

dfs(j,s);

}

int main()

{

int i,j,x;

cin>>n>>p;

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

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

{

cin>>x;

if(x) g[i][j]=1;

}

dfs(1,0);for(i=1;i<=n;i++) lt[i]=b[i];

for(i=1;i<=n;i++) if(i!=p)

{

memset(b,0,sizeof(b));

dfs(p,i);

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

if(j!=i && !b[j] && lt[j])

r[j][++l[j]]=i;

}

for(i=1;i<=n;i++) if(i!=p)

{

if(l[i]) for(j=1;j<=l[i];j++) cout<<r[i][j]<<" ";

else cout<<"No";

cout<<endl;

}

return 0;

}

#1 xyz32768@2016-12-22 06:32:45
回复 删除
不是,是O(N^3)
#2 xyz32768@2016-12-22 06:33:32
回复 删除
说错了,是N3
查看更多回复
提交回复