Description
给定一个有向图，若图无环，则将其进行拓扑排序并输出，否则输出IMPOSABLE。
Input
第一行为两个整数n(1<=n<=1000)、m(1<=m<=100000)；
之后m行，每行两个整数a、b(0 < a, b <= n)表示一条从a到b的有向边。
Output
若存在环，输出IMPOSABLE，否则输出一行用一个空格隔开的拓扑排序的结果，若存在多个结果，输出字典序最小的。
Sample Input
5 4
1 2
2 3
3 4
4 5
Sample Output
1 2 3 4 5
Source
Unknown
#include<bits/stdc++.h>
using namespace std;
int n, m, a, b, d[
1000+
8], num, cnt;
vector<
int>t[
1000+
8];
queue<
int>
q;
int ans[
1000+
8], sign[
1000+
8];
bool flag =
0;
priority_queue<
int, vector<
int>, greater<
int> >
you;
void bfs()
{
while(!
you.empty())
{
int f =
you.top();
you.pop();
if(flag)printf(
" ");
flag =
1;
printf("%d", f);
for(
int i =
0; i<t[f].size(); i++
)
{
d[t[f][i]]--
;
if(d[t[f][i]] ==
0 && !
sign[t[f][i]])
{
you.push(t[f][i]);
sign[t[f][i]] =
1;
}
// }
}
}
}
int get(
int miao)
//判环
{
int in[
1000+
8],si[
1000+
8];
for(
int i =
0; i <= miao; i++
)
{
in[i] =
d[i];
si[i] =
sign[i];
}
num =
miao;
while(!
q.empty())
{
int f =
q.front();
num--
;
q.pop();
for(
int i =
0; i<t[f].size(); i++
)
{
in[t[f][i]]--
;
if(!
in[t[f][i]] && !
si[t[f][i]])
{
q.push(t[f][i]);
si[t[f][i]] =
1;
}
}
}
return num;
}
int main()
{
while(~scanf(
"%d%d", &n, &m) && (n+
m))
{
memset(d, 0,
sizeof(d));
memset(sign, 0,
sizeof(sign));
for(
int i =
0; i<
1000+
8; i++
)t[i].clear();
while(!
q.empty())q.pop();
for(
int i =
0; i<m; i++
)
{
scanf("%d%d", &a, &
b);
t[a].push_back(b);//存图
d[b]++;
//入度++
}
for(
int i =
1; i <= n; i++
)
{
if(!d[i] && !sign[i])
//查找入度为0的节点，再插入队列，并标记它用过了
{
q.push(i);
you.push(i);
sign[i] =
1;
}
}
if(
get(n) ==
0)
//如果不存在环
{
bfs();//用bfs输出结果
}
else printf(
"IMPOSABLE\n");
}
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/10828022.html
相关资源：JAVA上百实例源码以及开源项目
