当前位置: 代码迷 >> 综合 >> POJ2367 Genealogical tree(拓扑排序)
  详细解决方案

POJ2367 Genealogical tree(拓扑排序)

热度:16   发布时间:2024-01-16 13:55:18.0

题意:

就是最简单的拓扑排序,裸题

要点:

裸题,直接模板一套就行


15174030 Seasonal 2367 Accepted 188K 0MS C++ 734B 2016-02-18 17:08:31
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int c[150],topo[150];
int t,n;
bool g[150][150];bool dfs(int u)
{c[u] = -1;for (int v = 1; v <= n; v++){if (g[u][v]){if (c[v] == -1) return false;else if (!c[v] && !dfs(v)) return false;}}c[u] = 1;topo[--t] = u;return true;
}
bool toposort()
{t = n;memset(c, 0, sizeof(c));for (int i = 1; i <= n; i++)if (!c[i] && !dfs(i))return false;return true;
}
int main()
{int u, v;scanf("%d", &n);memset(g, false, sizeof(g));for (u = 1; u <= n; u++){while (~scanf("%d", &v), v)g[u][v] = true;}if (toposort()){for (int i = 0; i < n - 1; i++)printf("%d ", topo[i]);printf("%d\n", topo[n - 1]);}return 0;
}


  相关解决方案