（以“分类:拓扑排序 ==摘要== {{信息题|Giving Awards|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70594#problem/F|2|100|数据类型|0|time=2015...”为内容创建页面） |
小 （→摘要： 字母） |
||
| 第1行： | 第1行： | ||
[[分类:拓扑排序]] | [[分类:拓扑排序]] | ||
==摘要== | ==摘要== | ||
| − | {{信息题|Giving Awards|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70594#problem/ | + | {{信息题|Giving Awards|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70594#problem/G|2|100|数据类型|0|time=2015-02-24 14:57:11}} |
| − | *来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70594 2015 Winter Warm up div2] | + | *来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70594 2015 Winter Warm up div2] G题 |
*原题链接：http://codeforces.com/problemset/problem/412/D | *原题链接：http://codeforces.com/problemset/problem/412/D | ||
| + | |||
==题意== | ==题意== | ||
求点集的遍历，要求不出现连续两项为(<m>a_i</m>,<m>b_i</m>)的连边（不会同时出现(<m>a_i</m>,<m>b_i</m>)和(<m>b_i</m>,<m>a_i</m>)） | 求点集的遍历，要求不出现连续两项为(<m>a_i</m>,<m>b_i</m>)的连边（不会同时出现(<m>a_i</m>,<m>b_i</m>)和(<m>b_i</m>,<m>a_i</m>)） | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 失误原因（初次提交分数） |
|---|---|---|---|---|---|
| Giving Awards | ★★☆☆☆ | 答案正确 | 100 | 2015-02-24 14:57:11 | 数据类型（0） |
求点集的遍历，要求不出现连续两项为(,
)的连边（不会同时出现(
,
)和(
,
)）
拓扑排序裸题，相当于逆向连边，拓扑排序即可（拓扑排序见Sgu/230）。由于内存卡的比较紧，用动态数组vector比较合适。
| 412D.cpp代码已折叠
展开折叠内容
|
|---|
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstring>
#define dsi(n) int n;scanf("%d",&n)
#define si(n) scanf("%d",&n)
#define f(i,n) for(int i=1;i<=n;++i)
#define fi(n) f(i,n)
#define f0(i,n) for(int i=0;i!=n;++i)
#define fd(i,n) for(int i=n;i>=1;--i)
#define ci const int&
#define foreach(i,s) for(typeof(s.begin()) i=s.begin();i!=s.end();++i)
#define c(x) const x&
bool visited[30010]={};
std::vector<int> map[30010]={};//改用vector而非map
int ans[30010]={},n,m,deep=0;
void dfs(ci at)
{
if(visited[at])return;
visited[at]=1;
foreach(i,map[at])
dfs(*i);
ans[++deep]=at;
}
int main()
{
si(n);si(m);
fi(m)
{
dsi(a);dsi(b);
map[b].push_back(a);
}
fi(n){
dfs(i);
}
if(deep==n)
{
fd(i,n)
printf("%d ",ans[i]);
exit(0);
}
std::cout<<-1;
return 0;
}
|
CloudLunar