首页 > 代码库 > SDUT OJ 2140 图结构练习——判断给定图是否存在合法拓扑序列
SDUT OJ 2140 图结构练习——判断给定图是否存在合法拓扑序列
#include<iostream>
#include<memory.h>
using namespace std;
int tp[11][11],visit[11];
int main()
{
int n,m,i,j,k,s,o,c;
int flag,count,a,b;
while(cin>>n>>m)
{
s=1;
o=0;
count=0;
memset(tp,0,sizeof(tp));
memset(visit,0,sizeof(visit));
for(i=1;i<=m;i++)
{
cin>>a>>b;
tp[a][b]=1;
}
/* for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(j==n)
cout<<tp[i][j]<<endl;
else
cout<<tp[i][j]<<" ";
}
*/
while(s)
{
flag=0;
c=0;
o++;
for(j=1;j<=n;j++)
{
for(i=1;i<=n;i++)
{
if(tp[i][j]==0 && visit[j]==0)
{
c++;
}
else
{
break;
}
}
if(c==n)
{
flag=0;
c=0;
}
else
{
flag=1;
c=0;
}
if(flag==0)
{
for(k=1;k<=n;k++)
tp[j][k]=0;
count++;
visit[j]=1;
}
}
if(o>n)
s=0;
else
s=1;
}
/* for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(j==n)
cout<<tp[i][j]<<endl;
else
cout<<tp[i][j]<<" ";
}
*/
if(count==n)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
/*
#include<iostream>
#include<memory.h>
using namespace std;
int tp[11][11],visit[11];
int n,m,u,v;
int dfs(int u)
{
visit[u]=-1;
for(v=1;v<=n;v++)
{
if(tp[u][v]==1)
{
if(visit[v]<0)
return 0;
else if(!visit[v] && !dfs(v))
return 0;
}
}
visit[u]=1;
return 1;
}
int topu()
{
for(u=1;u<=n;u++)
{
if(!visit[u])
{
if(!dfs(u))
return 0;
}
}
return 1;
}
int main()
{
int i;
while(cin>>n>>m)
{
memset(tp,0,sizeof(tp));
memset(visit,0,sizeof(visit));
for(i=0;i<m;i++)
{
cin>>u>>v;
tp[u][v]=1;
}
int k=topu();
if(k==0)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
return 0;
}
*/SDUT OJ 2140 图结构练习——判断给定图是否存在合法拓扑序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。