锐客网

  1. 首页 > it技术 > >

[codeforces 1385E] Directing Edges 变形的拓扑排序

codeforces

Codeforces Round #656 (Div. 3)参与排名人数11542早睡早起身体好
[codeforces 1385E]Directing Edges变形的拓扑排序
总目录详见https://blog.csdn.net/mrcrack/article/details/103564004
在线测评地址https://codeforces.com/contest/1385/problem/E

Problem Lang Verdict Time Memory
E - Directing Edges GNU C++17 Accepted 217 ms 13300 KB
题目大意：给一幅图，里面有有向边，有无向边，要求将所有无向边变成有向边，问能得到无环图吗，若不能，输出NO.若能，输出YES,以及所有的边(有向边).
看懂此文，需要拓扑排序基础。
样例模拟如下：
5 5 0 2 1 1 1 5 1 5 4 0 5 2 1 3 5YES 1 5 1 2 2 5 3 5 5 4

【[codeforces 1385E] Directing Edges 变形的拓扑排序】[codeforces 1385E] Directing Edges 变形的拓扑排序
文章图片

AC代码如下：
#include #define maxn 200010 struct node{ int to,next,w; }e[maxn<<1]; int head[maxn],q[maxn],vis[maxn],rd[maxn],tot,n,m,l[maxn],r[maxn],cnt; //rd[]入度，l[]有向边的左节点,r[]有向边的右节点 void add_edge(int u,int v,int w){//邻接表 tot++,e[tot].to=v,e[tot].w=w,e[tot].next=head[u],head[u]=tot; } void init(){ int cmd,u,v,i; scanf("%d%d",&n,&m); tot=cnt=0; //此处初始化很关键 for(i=1; i<=n; i++)head[i]=vis[i]=rd[i]=0; //初始化 for(i=1; i<=m; i++){ scanf("%d%d%d",&cmd,&u,&v); if(!cmd)add_edge(u,v,1),add_edge(v,u,1); //无向边 else add_edge(u,v,0),rd[v]++; //有向边 } } void solve(){ int h,t,u,v,w,b,i; h=t=1; for(i=1; i<=n; i++) if(!rd[i])q[t]=i,t++; //记录入度为0的点 while(h


    推荐阅读


    上一篇：uml|从 Java 代码逆向工程生成 UML 类图和序列图

    下一篇：[codeforces 1388C] Uncle Bogdan and Country Happiness 树的遍历+树的子树节点数量的变形