题目分析
一道模板题,具体分析见代码……
CODE
//刑场(拓扑排序模板)
/*
实施刑法的过程:
A---B
| |
C---D
从A出发,A没有入度,斩!
由于A有2条铁链,而A已经被斩了,所以铁链失去价值,去掉!
结果:
B
|
C---D
由于BC的情况与A相同,斩!
结果:
D
D的情况也相同了,也斩!
结果:
结束……
*/
#include<bits/stdc++.h>
using namespace std;
//安装铁链的工具
int h[5000000],ne[10000000],e[10000000];
int idx;
//安装铁链的函数,邻接表
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int n,m;//受刑的点的个数and铁链条数
int x,y;
int q[10000000],d[10000000];//斩首队列and各点出度
int tt=-1;//斩首队列里的点个数,初始化为-1
int hh;//当前所指的点在斩首队列里的位置
//实施刑法的函数
void topsort()
{
for(int i=1;i<=n;i++)//遍历一遍
{
if(d[i]==0)//这个点出度为0,压进队列,准备上断头台
{
q[++tt]=i;
}
}
while(tt>=hh)//指针未出界,不然可能会把无关的点斩掉
{
int a=q[hh];//把这个犯人压出来
hh++;//预计指向下一个
for(int i=h[a];i!=-1;i=ne[i])//让他与世隔绝,删除所以和他有关的链
{
int j=e[i];//这一条链是指向j的
d[j]--;//剪断!
if(d[j]==0)//如果另一个也没有出度了,斩!!!
{
q[++tt]=j;//压进队列
}
}
}
if(tt==n-1)//所有的点都被斩了QAQ
{
for(int i=0;i<n;i++)//公布死者名单
{
cout<<q[i]<<" ";
}
}
else//好可惜,没斩完
{
cout<<-1;
}
}
//从入狱到斩首函数
int main()
{
memset(h,-1,sizeof(h));
cin>>n>>m;//登记
for(int i=1;i<=m;i++)
{
cin>>x>>y;
d[y]++;//出度加一
add(x,y),add(y,x);
}
topsort();//实施刑法QAQ
return 0;//结束,等待下一批犯"点"
}