拓扑排序

2020-03-07

数据结构与算法

字数统计: 352字 | 阅读时长≈ 2分钟

拓扑排序的总结

题目传送门：POJ-2367 Genealogical tree

题目大意：

给定一个有向无环图，求拓扑排序序列

解题思路：

拓扑排序模板题

AC代码：

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int head[maxn], links, ans[maxn], pi, n, in[maxn], vis[maxn];
struct node
{
    int v, nex;
}edge[maxn];
void init()
{
    memset(head, 0, sizeof(head));
    memset(in, 0, sizeof(in));
    memset(vis, 0, sizeof(vis));
    links = 0;
    pi = 0;
}
void add_edge(int u, int v)
{
    edge[++links].v = v;
    edge[links].nex = head[u];
    head[u] = links;
}
void tsort()
{
    int i, j;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            if(!vis[j] && !in[j])
            {
                vis[j] = 1;
                ans[pi++] = j;
                break;
            }
        }
        int u = j;
        for(j = head[u]; j; j = edge[j].nex)
        {
            in[edge[j].v]--;
        }
    }
}
int main()
{
    int m, i, j, k;
    while(scanf("%d", &n) != EOF)
    {
        init();
        for(i = 1; i <= n; i++)
        {
            while(1)
            {
                scanf("%d", &j);
                if(j == 0)break;
                in[j]++;
                add_edge(i, j);
            }
        }
        tsort();
        for(i = 0; i < pi; i++)
        {
            if(i != 0)printf(" ");
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

1	#include <cstring>
2	#include <cstdio>
3	#include <algorithm>
4	using namespace std;
5	const int maxn = 100010;
6	int head[maxn], links, ans[maxn], pi, n, in[maxn], vis[maxn];
7	struct node
8	{
9	int v, nex;
10	}edge[maxn];
11	void init()
12	{
13	memset(head, 0, sizeof(head));
14	memset(in, 0, sizeof(in));
15	memset(vis, 0, sizeof(vis));
16	links = 0;
17	pi = 0;
18	}
19	void add_edge(int u, int v)
20	{
21	edge[++links].v = v;
22	edge[links].nex = head[u];
23	head[u] = links;
24	}
25	void tsort()
26	{
27	int i, j;
28	for(i = 1; i <= n; i++)
29	{
30	for(j = 1; j <= n; j++)
31	{
32	if(!vis[j] && !in[j])
33	{
34	vis[j] = 1;
35	ans[pi++] = j;
36	break;
37	}
38	}
39	int u = j;
40	for(j = head[u]; j; j = edge[j].nex)
41	{
42	in[edge[j].v]--;
43	}
44	}
45	}
46	int main()
47	{
48	int m, i, j, k;
49	while(scanf("%d", &n) != EOF)
50	{
51	init();
52	for(i = 1; i <= n; i++)
53	{
54	while(1)
55	{
56	scanf("%d", &j);
57	if(j == 0)break;
58	in[j]++;
59	add_edge(i, j);
60	}
61	}
62	tsort();
63	for(i = 0; i < pi; i++)
64	{
65	if(i != 0)printf(" ");
66	printf("%d", ans[i]);
67	}
68	printf("\n");
69	}
70	return 0;
71	}