人与狗做的网站,免费装修效果图大全,建设品牌型网站制作,qq钓鱼网站在线生成器文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴拓扑排序一、题目
1、原题链接 3696. 构造有向无环图 2、题目描述 给定一个由 n 个点和 m 条边构成的图。 不保证给定的图是连通的。 图中的一部分边的方向已经确定#…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴拓扑排序一、题目
1、原题链接 3696. 构造有向无环图 2、题目描述 给定一个由 n 个点和 m 条边构成的图。 不保证给定的图是连通的。 图中的一部分边的方向已经确定你不能改变它们的方向。 剩下的边还未确定方向你需要为每一条还未确定方向的边指定方向。 你需要保证在确定所有边的方向后生成的图是一个有向无环图即所有边都是有向的且没有有向环的图。 输入格式 第一行包含整数 T表示共有 T 组测试数据。 每组数据第一行包含两个整数 n,m。 接下来 m 行每行包含三个整数 t,x,y用来描述一条边的信息其中 t 表示边的状态如果 t0则表示边是无向边如果 t1则表示边是有向边。x,y 表示这条边连接的两个端点如果是有向边则边的方向是从 x 指向 y。 保证图中没有重边给定了 (x,y)就不会再次出现 (x,y) 或出现 (y,x) 和自环不会出现 xy 的情况。 输出格式 对于每组数据如果无法构造出有向无环图则输出一行 NO。 否则先输出一行 YES随后 m 行每行包含两个整数 x,y用来描述最终构造成的有向无环图中的每条边的具体方向x 指向 y边的先后顺序随意。 注意已经确定方向的边不能更改方向。 如果答案不唯一输出任意合理方案均可。 数据范围 对于前三个测试点1≤n,m≤10。 对于全部测试点1≤T≤200002≤n≤2×1051≤m≤min(2×105,n(n−1)/2)0≤t≤11≤x,y≤n。 保证在一个测试点中所有 n 的和不超过 2×105所有 m 的和不超过 2×105。 输入样例 4
3 1
0 1 3
5 5
0 2 1
1 1 5
1 5 4
0 5 2
1 3 5
4 5
1 1 2
0 4 3
1 3 1
0 2 3
1 2 4
4 5
1 4 1
1 1 3
0 1 2
1 2 4
1 3 2输出样例 YES
3 1
YES
2 1
1 5
5 4
2 5
3 5
YES
1 2
3 4
3 1
3 2
2 4
NO二、解题报告
1、思路分析 思路来源y总yyds y总yyds 1如果给定图中存在回路即无法构成构成拓扑序列则无论怎样为无向边添加方向都不可能无环所以此时无解。 2如果给定的图中不存在回路即存在拓扑序列则可以将与无向边相连的点在拓扑序列中前面的点指向后面的点这样为每条边添加方向不会存在环。 3按上述模拟先输出所有有向边然后再按2输出所有无向边同时为无向边添加方向。
2、时间复杂度
拓扑排序时间复杂度为O(nm)n为点数m为边数
3、代码详解
/*注使用cin、cout最后一个测试数据会超时*/
#include iostream
#include queue
#include cstring
#include algorithm
using namespace std;
const int N200010,MN; //N代表点数M代表边数
//邻接表存储有向边
int h[N],e[M],ne[M],idx; //h[]存储每个点的第一条边的idxe[]存储每条边的终点ne[]存储每个点同起点下一条边的idxidx为边的编号
int d[N]; //记录每个点的入度
int ans[N]; //记录拓扑序列
int pos[N]; //记录每个点在拓扑排序中的位置
int n,m,T;
//存储无向边
struct Edge{int a,b;
}edge[M];
//邻接表中添加一条边
void add(int a,int b){e[idx]b;ne[idx]h[a];h[a]idx;
}
//拓扑排序
bool tp(){queueint q;int ord0,num0; //ord记录每个点入队顺序也就是在拓扑序列中的先后顺序for(int i1;in;i){if(d[i]0) q.push(i),pos[i]ord;}while(!q.empty()){int tq.front();q.pop();ans[num]t;for(int ih[t];i!-1;ine[i]){int je[i];d[j]--;if(d[j]0) q.push(j),pos[j]ord;}}return numn;
}
int main(){cinT;while(T--){memset(h,-1,sizeof h);memset(d,0,sizeof d);idx0;scanf(%d%d,n,m);int t,x,y;int cnt0;while(m--){scanf(%d%d%d,t,x,y);if(t0) edge[cnt]{x,y};else{add(x,y);d[y];}}if(!tp()) puts(NO);else{puts(YES);//先输出所有有向边for(int i1;in;i){for(int jh[i];j!-1;jne[j]){printf(%d %d\n,i,e[j]);}}//输出无向边的同时给边“确定方向”for(int i0;icnt;i){int xedge[i].a,yedge[i].b;if(pos[x]pos[y]) swap(x,y); //拓扑序列中前面的点指向后面的点printf(%d %d\n,x,y);}}}return 0;
}三、知识风暴 拓扑排序 拓扑序列满足如果存在vi到vj的路径则顶点vi必然在顶点vj之前。拓扑排序过程 从有向图中选择一个没有前驱即入度为0的点并且输出。从图中删去该顶点并且删去从该顶点发出的全部有向边。重复上述两步直到剩余的图中不再存在没有前驱的顶点为止。
