本题思路:有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int h[N],e[N],ne[N],idx;
int n,m;
int q[N],d[N];//q表示队列,d表示点的入度
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
bool topsort()
{
int hh=0,tt=-1;
for(int i=1;i<=n;i++)
if(!d[i])
q[++tt]=i;//将入度为零的点入队
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
d[j]--;//删除点t指向点j的边
if(d[j]==0)//如果点j的入度为零了,就将点j入队
q[++tt]=j;
}
}
return tt==n-1;
//表示如果n个点都入队了话,那么该图为拓扑图,返回true,否则返回false
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof(h));//如果程序时间溢出，就是没有加上这一句
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);//因为是a指向b,所以b点的入度要加1
d[b]++;
}
if(topsort())
{
for(int i=0;i<n;i++)
printf("%d ",q[i]);
//经上方循环可以发现队列中的点的次序就是拓扑序列
//注:拓扑序列的答案并不唯一,可以从解析中找到解释
puts("");
}
else
puts("-1");
return 0;
}
我发现大佬们的解析太优秀了，我课没听懂从不回放，直奔解析。
我也是哈哈，课听一遍就不听了，直接跑来看大佬们的解析
hh我也是
h[ ]数组具体是干嘛的，有大佬能解释一下吗
邻接表的主链表，用来存储下标的。具体可以看一下第二章的散列哈希中的拉链法，跟着Y总绘图感受一下。相当于子链表的表头。
一开始还执着于为啥不用stl的队列，后来发现模拟队列还是有模拟队列的好处的
请问是为什么呀！！！有啥好处
stl的队列不方便遍历
数组直接从队头遍历到队尾就完了
好的谢谢~
大佬请问你写的这句话”从后指向前，必定形成环这句话“我觉得不太对，
提示：关于图的存储方法不明白的同学如果搜邻接表存储图搜不到想要的答案，搜一下“链式前向星”
为什么tt要初始化为-1，0不行吗
可以，只是个人的习惯问题
为什么是tt==n-1呀
因为刚开始的tt=-1,如果有n个点都进入了队列,那么tt=n-1
因为下标是从0开始滴，0-n-1是n个数字
在循环中d[j]–;但是在这里的j不是在不断变化吗？这个循环没有听懂
j应该是不变的吧
循环中 j是变的
这里的一遍循环j减去1，结果分为两种情况等于0或者不等于0；
若等于零就说明这个点j在上一个删去点的拓扑序后面，
若不等于零就说明点j还有入度，后面继续遍历后的某个点会删去这个j点，导致点j的入度为0，进入拓扑序
循环中j的变化的实质上是在确定j在拓扑序中的位置
请问怎么是解决重边和自环问题的
为什么要 d[j]–;//删除点t指向点j的边
请问这题时间复杂度是多少
for(int i=1;i<=n;i)
if(!d[i])
q[tt]=i;//将入度为零的点入队
d[0]不是入度为零吗
大佬解析太优秀了，听了5遍都没懂终于在大佬这里看懂了
真假y总！ hhhhh
Orz
for(int i=h[t];i!=-1;i=ne[i])
请问这句是什么意思呢
如果下一个节点非空， 那么就指向下一个节点
谢谢
请问以下重边的情况怎么解决啊
重边和其他所有边都一样，删两次就行了， 没有影响的
very good
您真是太棒啦
记录美好生活
%%%%%