CodeForces/412D

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	失误原因（初次提交分数）
Giving Awards	★★☆☆☆	答案正确	100	2015-02-24 14:57:11	数据类型（0）

• 来自寒假练习：2015 Winter Day 1 div1 G题
• 原题链接：http://codeforces.com/problemset/problem/412/D

题意

求点集的遍历，要求不出现连续两项为(,)的连边（不会同时出现(,)和(,)）

题解

拓扑排序裸题，相当于逆向连边，拓扑排序即可（拓扑排序见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; }