首页 > 代码库 > vijos 拓扑编号
vijos 拓扑编号
描述
H国有n个城市,城市与城市之间有m条单向道路,满足任何城市不能通过某条路径回到自己。
现在国王想给城市重新编号,令第i个城市的新的编号为a[i],满足所有城市的新的编号都互不相同,并且编号为[1,n]之间的整数。国王认为一个编号方案是优美的当且仅当对于任意的两个城市i,j,如果i能够到达j,那么a[i]应当<a[j]。
优美的编号方案有很多种,国王希望使1号城市的编号尽可能小,在此前提下,使得2号城市的编号尽可能小...依此类推。
格式
输入格式
第一行读入n,m,表示n个城市,m条有向路径。
接下来读入m行,每行两个整数:x,y
表示第x个城市到第y个城市有一条有向路径。
输出格式
输出一行:n个整数
第i个整数表示第i个城市的新编号a[i],输出应保证是一个关于1到n的排列。
样例1
样例输入1
5 4
4 1
1 3
5 3
2 5
Copy
样例输出1
2 3 5 1 4
Copy
限制
每个测试点1s
提示
30%的测试点满足:n <= 10, m <= 10
70%的测试点满足:n <= 1000, m <= 10000
100%的测试点满足:n <= 100000, m <= 200000
输入数据可能有重边,可能不连通,但保证是有向无环图。
来源
Topcoder
/*逆拓扑+贪心,从后往前,先找编号最大的 证明: 假设我们按逆拓扑排序的方法求出了一个拓扑序列(把得到的反序列正过来),记为A。 假设最优解的拓扑序列是B。 从后往前比较AB,设在位置k,AB第一次出现不同。即A[k]!=B[k],A[p]=B[p]. 显然根据我们的贪心策略"每次取的是编号最大的",有A[k]>B[k]. 那么我们在B中取寻找A[k],即找到B[p]=A[k]. 然后把B中B[p],B[p+1]...B[k]这一段拿出来,记为序列C。 因为B[p]=A[k] , 把B[p]换成A[k],C=A[k],B[p+1]....B[k]. 很显然在C中A[k]不是最小的,因为至少B[k]比它小。 假设C中最小的是B[q],那么我们可以构造出一个序列D. D=B[p+1],B[p+2]...B[q],A[k],B[q+1]...B[k]. (实质就是把A[k]移到B[q]的后面) 显然这个序列会比序列C更优,因为B[q]的名次靠前了一名。 那么如果把C换成D会更优,与B是最优解矛盾。 那么怎么知道序列D一定是合法的呢?因为如果A[k]恰好是B[p+1]的前驱,那么就不能把A[k]移走。 所以我们回到序列A,序列A中A[k]是AB序列从右往左第一个不同的元素,那么在A中,B[p+1]肯定是在A[k]前面的,所以A[k]不可能是B[p+1]的前驱。 综上,我们得到的答案就是最优解。 如果不理解,按照样例举个例子 4 -> 1 -> 3 <-5 <-2; 如果贪心,每次找入度为0的点,若有多点,找编号小的点: 第一次找到 2; 第二次找到 4; 第三次找到 1; 第四次找到 5; 第五次找到 3; 这显然是错误的: 按照上面方法 逆拓扑,从后往前,先找编号最大的 1ci find 3, 3 number 5; 2ci find 5, 5 number 4; 3ci find 2, 2 number 3; 4ci fine 1, 1 number 2; 5ci fine 4, 4 number 1; fit answer; */ #include<iostream> #include<cstdio> #include<vector> #include<queue> using namespace std; const int maxn = 100000 + 10; const int maxm = 200000 + 10; int n, m; int cloc; int cnt[maxn], id[maxn]; vector<int> G[maxn]; priority_queue<int> Q; int main () { scanf("%d%d",&n,&m); while (m--) { int u, v; scanf("%d%d", &u, &v); u--; v--; cnt[u]++; G[v].push_back(u); } for (int i = 0; i < n; i++) if (!cnt[i]) Q.push(i); cloc = n; while (!Q.empty()) { int u = Q.top(); Q.pop(); id[u] = cloc--; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; cnt[v]--; if (cnt[v] == 0) Q.push(v); } } for (int i = 0; i < n; i++) printf("%d ", id[i]); return 0; }
vijos 拓扑编号
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。