hihoCoder 1174 : 拓扑排序·一
2024-08-24 23:18:34
题目链接:http://hihocoder.com/problemset/problem/1174
题目是中文题面我就不说题意了,要看题面的请点击上方链接~
代码实现如下:
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std; const int maxn = 1e5 + ;
int t, n, m, num, u, v;
int InDeg[maxn];
vector<int> G[maxn]; bool topsort() {
num = ;
queue<int> q;
for(int i = ; i <= n; i++) {
if(InDeg[i] == ) {
q.push(i);
}
}
int x;
while(!q.empty()) {
x = q.front(), q.pop();
num++;
int s = G[x].size();
for(int i = ; i < s; i++) {
if(--InDeg[G[x][i]] == ) {
q.push(G[x][i]);
}
}
}
return num == n;
} int main() {
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) {
G[i].clear();
InDeg[i] = ;
}
for(int i = ; i < m; i++) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
InDeg[v]++;
}
if(topsort()) {
printf("Correct\n");
} else {
printf("Wrong\n");
}
}
return ;
}
最新文章
- 转:用C++实现的一种插件体系结构-----概述
- C# UdpClient使用Receive和BeginReceive接收消息时的不同写法
- 从 datetime2 数据类型到 datetime 数据类型的转换产生一个超出范围的值
- 几个Unicode新知识:扩展ANSI有很多种(256个字符),Unicode表示ANSI字符时高字节为0,Unicode不包括古代字符
- phpcms学习总结
- redhat 7.2 配置yum源
- 【Stirling Number I】
- jQuery 的 $(";someobjectid”).event() 的绑定
- DP练习(初级):ZigZag
- Hibernate框架后续
- JS的作用域浅谈
- 防盗链[referer]
- ssh: Could not resolve hostname git.*****-inc.com : Temporary failure in name resolution fatal: The remote end hung up unexpectedly
- 易忘&;有用 的冷门Anaconda命令
- Ubuntu18.04安装搜狗拼音输入法皮肤透明解决方法
- python 全栈开发,Day7(元组转换,列表以及字典的坑,集合,关系测试,深浅copy,编码补充)
- 用gradle打包可运行jar
- Oracle 12C -- 清空audit记录
- 网页IE轻松调用VLC播放器实现监控(组件+方法大全)【转】
- springMVC与Struts2区别
热门文章
- 【vue】vue组件的自定义事件
- PHP上传文件限制的大小
- Arrays.toString 如果传入的是对象 那么调用的是此对象的toString
- 【Java】Java CSV操作代码
- BZOJ4951 Wf2017Money for Nothing(决策单调性)
- C 程序结构——Day01
- P1107 [BJWC2008]雷涛的小猫
- Codeforces Round #362(Div1) D Legen...(AC自动机+矩阵快速幂)
- 3.7 TCP拥塞控制
- 史上最全面,清晰的SharedPreferences解析