(以“分类:拓扑排序 ==摘要== {{信息题|Giving Awards|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70594#problem/F|2|100|数据类型|0|time=2015...”为内容创建页面)
 
摘要: 比赛名
 
(未显示1个用户的1个中间版本)
第1行: 第1行:
 
[[分类:拓扑排序]]
 
[[分类:拓扑排序]]
 
==摘要==
 
==摘要==
{{信息题|Giving Awards|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70594#problem/F|2|100|数据类型|0|time=2015-02-24 14:57:11}}
+
{{信息题|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] F题
+
*来自寒假练习:[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70594 2015 Winter Day 1 div1] 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>))

2015年2月27日 (五) 15:44的最后版本

摘要

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

题意

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

题解

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

著作权声明[编辑]

关于[编辑]