ACM1258邻接表
2024-08-22 19:03:13
教训:使用邻接表的时候一定要把邻接表的结构组定义的足够大,不能仅仅等于节点的个数,因为线段的数量往往远超过节点的数量。
这个题目是拓扑排序练习,提高下理解。
#include<iostream>
using namespace std;
struct TOPO
{
int from,to,next;
};
TOPO p[];//这里要定义的足够大才行
int head[];//它和上面的是同步的大小才好
int *in,*use;
int cnt;
void Merge(int f,int t)
{
p[cnt].from=f;
p[cnt].to=t;
p[cnt].next=head[f];
head[f]=cnt;
cnt++;
}
int main()
{
int n,m;
while(cin>>n>>m)
{
cnt=;
in=new int[n+];
use=new int[n+];
for(int i=;i<=n;i++)
{
in[i]=;
use[i]=;
head[i]=-;
}
int a,b;
for(int i=;i<=m;i++)
{
cin>>a>>b;
Merge(a,b);
in[b]++;
//out[a]++;
}
int index=; for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(!use[j]&&in[j]==)
{
if(i>)cout<<" ";
index=j;
use[j]=;
cout<<j;
break;
}
}
for(int j=head[index];j!=-;j=p[j].next)
{
in[p[j].to]--;
}
}
cout<<endl;
delete []in;
delete []use;
}
return ;
}
最新文章
- java在类定义时对hashset的便捷初始化方法
- MySql技巧个人笔记
- 【转】 MySQL与PostgreSQL:该选择哪个开源数据库?哪一个更好?
- 【英语】Bingo口语笔记(19) - 如何用英语叙旧
- linux网站推荐
- Centos6.4最小化安装后使用xfce桌面环境
- Telerik 控件事例(鼠标拖动行,拖动列,设置行对齐,行宽,是否显示)
- bzoj1823
- 【转载】Oracle层次查询和分析函数
- Java并发3-多线程面试题
- error: C2664: “zajiao::zajiao(const zajiao &;)”: 无法将参数 1 从“const char [12]”转换为“char *”
- 让EF支持sql语句
- linux iptables 配置
- ReactiveSwift源码解析(十一) Atomic的代码实现以及其中的Defer延迟、Posix互斥锁、递归锁
- C#的数据类型总结(1)
- JAVA 多线程(3)
- DDD实践:领域事件
- GBDT和随机森林的区别
- Lustre文件系统部署和应用探索
- Java连接oracle数据库的两种常用方法