建一个简单的网站多少钱,上海发布官网app下载,txt怎么做pdf电子书下载网站,教育网站建站需求题干#xff1a;
Applese 有一个QQ群。在这个群中#xff0c;大家互相请教问题。如 b 向 a 请教过问题#xff0c;就把 a 叫做是 b 的老板。这样一个群中就会有很多老板。 同时规定#xff1a;如果 a 是 b 的老板#xff0c;b 是 c 的老板#xff0c;那么…题干
Applese 有一个QQ群。在这个群中大家互相请教问题。如 b 向 a 请教过问题就把 a 叫做是 b 的老板。这样一个群中就会有很多老板。 同时规定如果 a 是 b 的老板b 是 c 的老板那么 a 也是 c 的老板。 为了不破坏群里面和谐交流的氛围Applese 定了一个群规不允许出现 a 既是 b 的老板 b 又是 a 的老板。 你需要帮助 Applese 判断大家是否遵守了群规。
输入描述:
第一行两个整数 n, m表示群里的人数以及请教问题的数量。
接下来 m 行每行两个整数 a, b表示 a 是 b 的老板即 b 向 a 请教了一个问题。
注无论是否违反了群规a 都会成为 b 的老板。
输出描述:
对于每次提问输出一行Yes表示大家都遵守了群规反之输出No。
示例1
输入
复制
4 4
1 2
2 3
3 1
1 4
输出
复制
Yes
Yes
No
No
备注:
1≤n≤1051≤n≤105
1≤m≤2⋅1051≤m≤2⋅105
1≤a,b≤n 解题报告 本来想搞一个种类并查集、、后来交上去wa了就没在管其实是个二分check、、、不难的题check用topu一下就行了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
struct Edge{int u,v;
} e[MAX];
int n,m;
int in[MAX];
vectorint vv[MAX];
bool ok(int x) {for(int i 1; in; i) in[i] 0,vv[i].clear();for(int i 1; ix; i) {in[e[i].v];vv[e[i].u].pb(e[i].v);}queueint q;for(int i 1; in; i) {if(in[i] 0) q.push(i);}int cnt 0;while(q.size()) {int cur q.front();q.pop();int up vv[cur].size();cnt;for(int i 0; iup; i) {int to vv[cur][i];in[to]--;if(in[to] 0) q.push(to);}}if(cnt ! n) return 0;else return 1;
}
int main()
{cinnm;for(int x,y,i 1; im; i) {scanf(%d%d,x,y);e[i] {x,y};}int l 1,r m;int mid (lr)1;int ans ;while(lr) {mid (lr)1;if(ok(mid)) ans mid,l mid1;else r mid-1;}for(int i 1; ians; i) printf(Yes\n);for(int i ans1; im; i) printf(No\n);return 0 ;}
