CF 915 D 拓扑排序
2024-10-19 03:36:34
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 142857;
int t,n,m,k,x,u,v,w,num,flag;
vector<int> G[maxn];
int inDeg[maxn], ruDeg[maxn];
int virus[maxn];
queue<int> q;
bool topSort()
{
num=0;
while(!q.empty()) q.pop();
for(int i=1;i<=n;i++) if(!inDeg[i]) q.push(i);
while(!q.empty())
{
int now = q.front();
q.pop();
num++;
for(int i=0;i<G[now].size();i++)
{
int nxt = G[now][i];
if(--inDeg[nxt] == 0) q.push(nxt);
}
}
if(num == n) return true;
else return false;
}
int main()
{
while(~ scanf("%d%d",&n,&m) )
{
memset(inDeg,0,sizeof(inDeg));
memset(ruDeg,0,sizeof(ruDeg));
for(int i=1;i<=n;i++) G[i].clear();
while(m--)
{
scanf("%d%d",&u,&v);
G[u].push_back(v);
inDeg[v]++;
ruDeg[v]++;
}
if(topSort())
{
puts("YES");
continue;
}
else
{
flag = 0;
for(int i=1; i<=n; i++)
{
memcpy(inDeg,ruDeg,sizeof(ruDeg));
if(inDeg[i] >= 1)
{
inDeg[i]--;
if(topSort())
{
flag = 1;
puts("YES");
break;
}
}
}
}
if(flag == 0) puts("NO");
}
}
最新文章
- es6之let和const
- 【poj2151】 Check the difficulty of problems
- C#实现约瑟夫环问题
- android activity的启动方式
- 什么是xmlschema
- not only ... but also
- 玩转React样式
- 移动端的日期插件 mobiscroll 2.14.4 破解版
- 漫话JavaScript与异步&#183;第一话——异步:何处惹尘埃
- hdu-4638-Group(树状数组)
- int string convert
- Codeforces 540D Bad Luck Island
- hadoop 主节点存储告警
- C#与Arduino通过串口通信来控制LED灯的状态
- getNextElement( )函数——获取下一个特定的元素节点
- linux 下 用phpmailer类smtp发送邮件始终不成功,提示:ERROR: Failed to co
- HBase replication
- 监督学习——logistic进行二分类(python)
- centos7使用wordpress布署网站(2)
- 详细理解servlet实现的三种方式和生命周期