本题属于最基础的拓扑排序。大意就是,给出一个数n, 然后底下n行,编号1到n, 每行输入几个数,保证结果中该行的编号要在这几个数前面。
/*
ID: sdj22251
PROG: calfflac
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 100000000
#define LOCA
#define PI acos(-1.0)
using namespace std;
int n, m;
int in[201];
int ans[201];
vector<int>v[201];
void topsort()
{
int i, ct = 0;
queue<int>q;
for(i = 1; i <= n; i++)
{
if(in[i] == 0)
q.push(i);
}
while(!q.empty())
{
int first = q.front();
ans[ct++] = first;
q.pop();
int size = v[first].size();
for(i = 0; i < size; i++)
{
int can_reach = v[first][i];
in[can_reach]--;
if(in[can_reach] == 0)
q.push(can_reach);
}
}
}
int main()
{
#ifdef LOCAL
freopen("ride.in","r",stdin);
freopen("ride.out","w",stdout);
#endif
int i, tmp;
scanf("%d", &n);
for(i = 1; i <= n; i++)
{
while(1)
{
scanf("%d", &tmp);
if(tmp == 0)
break;
v[i].push_back(tmp);
in[tmp]++;
}
}
topsort();
for(i = 0; i < n - 1; i++)
printf("%d ", ans[i]);
printf("%d\n", ans[n - 1]);
return 0;
}
分享到:
相关推荐
北大POJ2255-Tree Recovery 解题报告+AC代码
poj 2201 Cartesian Tree.md
NULL 博文链接:https://200830740306.iteye.com/blog/603488
Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is ...
poj 1091 拓扑排序加上foyld_warshall算法实现
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
poj 1909 Marbles on a tree.md
建树,树的遍历访问,联系数据结构不错的题目
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 1308 Is It A Tree_.md
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
POJ上的一道题,我感觉挺难的。分享给大家,这是利用拓扑排序实现,也算是拓扑排序的一道例题。有助于大家对拓排的理解
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
NULL 博文链接:https://128kj.iteye.com/blog/1754756
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告