Educational Codeforces Round 25 E. Minimal Labels 拓扑排序+逆向建图
1 second
256 megabytes
standard input
standard output
You are given a directed acyclic graph with n vertices and m edges. There are no self-loops or multiple edges between any pair of vertices. Graph can be disconnected.
You should assign labels to all vertices in such a way that:
- Labels form a valid permutation of length n — an integer sequence such that each integer from 1 to n appears exactly once in it.
- If there exists an edge from vertex v to vertex u then labelv should be smaller than labelu.
- Permutation should be lexicographically smallest among all suitable.
Find such sequence of labels to satisfy all the conditions.
The first line contains two integer numbers n, m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105).
Next m lines contain two integer numbers v and u (1 ≤ v, u ≤ n, v ≠ u) — edges of the graph. Edges are directed, graph doesn't contain loops or multiple edges.
Print n numbers — lexicographically smallest correct permutation of labels of vertices.
3 3
1 2
1 3
3 2
1 3 2
4 5
3 1
4 1
2 3
3 4
2 4
4 1 2 3
5 4
3 1
2 1
2 3
4 5
3 1 2 4 5
题意:给你n个点,m条边的有向无环图,一条边u->v表示u的权值小于v的权值;求字典序最小的方案;
思路:反向建图,使得大的点的权值更大;类似与hdu 4857;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define LL long long
#define pi (4*atan(1.0))
#define eps 1e-14
#define bug(x) cout<<"bug"<<x<<endl;
const int N=1e5+,M=2e6+,inf=1e9+;
const LL INF=1e18+,mod=1e9+; vector<int>edge[N];
int du[N],ans[N];
priority_queue<int>q;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
edge[v].push_back(u);
du[u]++;
}
for(int i=;i<=n;i++)
if(!du[i])q.push(i);
int s=n;
while(!q.empty())
{
int x=q.top();
q.pop();
ans[x]=s--;
for(int i=;i<edge[x].size();i++)
{
int v=edge[x][i];
du[v]--;
if(!du[v])q.push(v);
}
}
for(int i=;i<=n;i++)
printf("%d ",ans[i]);
return ;
}
最新文章
- 【msql】关于redo 和 undo log
- Atitti usrQBf1801 翻页控件规范 &#160;v2
- Hibernate SQL 方言(hibernate.dialect)
- QQReg.java
- python中的md5加密
- click 绑定(二)带参数的click 事件绑定
- HDU 1856
- 从Eclipse到Android Studio经历
- 转:100个高质量Java开发者博客
- ExtJs4 笔记(10) Ext.tab.Panel 选项卡
- 程序猿学英语—In July the English learning summary
- 金蝶K3无法创建数据库,请查看该文件夹的错误的解决方法。
- 原生ajax实现http请求
- QGIS2.18.0的精简编译
- Maven构建真正的J2EE项目
- linux常用的压缩与解压缩命令
- 局部内部类访问它所在方法的局部变量时,要求该局部变量必须声明为final的原因
- 微信授权登录mock(在没有真实微信账号的情况下测试大量微信账户授权登录的情况)
- [Leetcode easy]存些水题34、20、700
- 原型链上的call方法集合
热门文章
- [转载]基于 Token 的身份验证
- Servlet向JSP过渡
- ==和equasl、hashmap原理(***)
- self: 限制并发量asyncio
- 上传代码到github的步骤
- 你不知道的JavaScript(1)LHS查询和RHS查询
- cJSON库的简单介绍及使用
- 使用SimpleDateFormat时的日期和时间模式
- 关于BOARD_SYSTEMIMAGE_PARTITION_SIZE【转】
- Visual Studio Code 的 launch.json 解析