hiho拓扑排序专题 ——第四十八、四十七周
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了hiho拓扑排序专题 ——第四十八、四十七周,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3012字,纯文字阅读大概需要5分钟。
内容图文
![hiho拓扑排序专题 ——第四十八、四十七周](/upload/InfoBanner/zyjiaocheng/1138/37240e310f4b40fd8c68317297ffddc0.jpg)
分析:
此题就是求一个有向图中是否存在环。 如存在环则输出”Wrong”, 若不存在环, 说明课程安排的合理,输出”Correct”。
题中的提示说的已经十分清楚了。
总的来说就是:
① 找出入度为0的点(说明该点没有前驱),把该点放入集合T中。 把所有从该点出发的边都删除;
② 遍历剩余的点, 找出入度为0 的点, 重复①操作。
③直到不存在入度为0的点。 结束。如果此时集合T中包含所有的点, 那么该图不存在环, 否则存在环。
注意:1、执行操作①时, 在删除边时(u, v),同时更新与其相关点的入度(du[v]–);
2、 在执行操作②时, 需要遍历所有点, 点少的时候可行, 点多的话很容易超时。 所以题目的提示中告诉了一个好办法就是: 执行操作①更新相关点的入度时 直接判断一下是否为0, 若为零则入队列。 这样会省很多时间。
如下图例子:
开始点1入度为0, 点1加入集合T, 删除从1出发的边; 更新相关点的入度, 点2、3的入度都变为0了 , 2、3入队列;
再依次对点2、3进行①操作, 2、3加入T, 删除边(2, 4), (3, 4), 此时没有其他点入度为0了, 结束操作, T中未包含所有点, 说明该图中有环;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using
namespace
std;
int t, n, m, sum, du[100005];
vector<int> vec[100005];
int ac()
{
queue<int> q;
for(int i = 1; i <= n; i++)//遍历一边所有点, 把入度为0的点,全加入队列q中
{
if(du[i] == 0)
q.push(i);
}
while(!q.empty())
{
int tem = q.front();//在队列中取出一个入度为0的点
q.pop();
sum++;
//把所有从tem出发的边(tem, v)删除并更新du[], for(int i = 0; i < vec[tem].size(); i++)
{
du[vec[tem][i]]--;
if(du[vec[tem][i]] == 0)//若点vec[tem][i]入度更新后为0, 则入队列
q.push(vec[tem][i]);
}
vec[tem].clear();
}
if(sum == n) return1;
elsereturn0;
}
int main()
{
cin >> t;
while(t--)
{
scanf("%d%d", &n, &m);
//用vec[]来存边for(int i = 1; i <= n; i++) vec[i].clear();
memset(du, 0, sizeof(du));//初始化入度, 置为0;for(int i = 1; i <= m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
vec[x].push_back(y); // 加入边
du[y]++; //记录入度
}
sum = 0;
int ans = ac();
if(ans == 1)
printf("Correct\n");
elseprintf("Wrong\n");
}
return0;
}
分析:
和上一道差不多, 只是多了一项就是记录每个点的病毒数。 每个点的病毒数 = 自身病毒数 + 所有能够达到它的节点病毒数之和( 就是所有它前驱点的病毒数的和)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
using
namespace
std;
constint mod = 142857;
int n, m, k, sum, virus[100005], du[100005];
vector<int> vec[100005];
void ac()
{
queue<int> q;
for(int i = 1; i <= n; i++)
{
if(du[i] == 0)
q.push(i);
}
while(!q.empty())
{
int tmp = q.front(); q.pop();
sum = (sum + virus[tmp]) % mod;
//把所有前驱点为 tmp 的点的病毒数都加上 tmp的病毒数for(int i = 0; i < vec[tmp].size(); i++)
{
int b = vec[tmp][i];
virus[b] = (virus[tmp] + virus[b]) % mod;// 此处也一定要取模,
du[b]--;
if(du[b] == 0)
q.push(b);
}
vec[tmp].clear();
}
}
int main()
{
while(scanf("%d%d%d", &n, &m, &k) != EOF)
{
memset(virus, 0, sizeof(virus));
memset(du, 0, sizeof(du));
for(int i = 1; i <= n; i++) vec[i].clear();
for(int i = 1; i <= k; i++)
{
int x;
scanf("%d", &x);
virus[x]++;
}
for(int i = 1; i <= m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
vec[x].push_back(y);
du[y]++;
}
sum = 0;
ac();
printf("%d\n", sum);
}
return0;
}
原文:http://blog.csdn.net/wangdan11111/article/details/46547347
内容总结
以上是互联网集市为您收集整理的hiho拓扑排序专题 ——第四十八、四十七周全部内容,希望文章能够帮你解决hiho拓扑排序专题 ——第四十八、四十七周所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。