正文
Applese的QQ群-（拓扑+二分）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
链接：https://ac.nowcoder.com/acm/contest/330/F
来源：牛客网
题目描述 
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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxx=1e5+;
int n,m,a,b;
int deg[maxx];
vector<int>vec[maxx];
struct node
{
int a;
int b;
};
node edge[*maxx];
queue<int>q;bool tuopu()
{
while(!q.empty()) q.pop();
for(int i=;i<=n;i++)
if(deg[i]==)
q.push(i);
int now;//当前头结点
while(!q.empty())
{ now=q.front();
q.pop();
for(int i=;i<vec[now].size();i++)
{
if( --deg[ vec[now][i] ]== )
q.push(vec[now][i]);
}
}
for(int i=;i<=n;i++)//检查有没有入度不为0的结点，有的话就是环了
if(deg[i])
return false;
return true;
}bool check(int x)
{
memset(deg,,sizeof(deg));
for(int i=;i<=n;i++) vec[i].clear();
for(int i=;i<=x;i++)//建图
{
node e=edge[i];
deg[e.a]++;
vec[e.b].push_back(e.a);
}
return tuopu();
}int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=;i<=m;i++)
scanf("%d%d",&edge[i].a,&edge[i].b);
int l=,r=m;
int mid;
int ans;
while(l<=r)
{
mid=(l+r)/;
if( check(mid) )
{
ans=mid;
l=mid+;
}
else
{
r=mid-;
}
}
for(int i=;i<=m;i++)
if(i<=ans)
printf("Yes\n");
else
printf("No\n");
} return ;
}/// a b表示a是b的老板，规定箭头由b指向a，a的入度+1，a←b,b的邻接表压入a
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
4 4
1 2
2 3
3 1
1 4
输出Yes
Yes
No
No
Yes
Yes
No
No
备注:
1≤n≤1051≤n≤105
1≤m≤2⋅1051≤m≤2⋅105
1≤a,b≤n
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxx=1e5+;
int n,m,a,b;
int deg[maxx];
vector<int>vec[maxx];
struct node
{
int a;
int b;
};
node edge[*maxx];
queue<int>q;bool tuopu()
{
while(!q.empty()) q.pop();
for(int i=;i<=n;i++)
if(deg[i]==)
q.push(i);
int now;//当前头结点
while(!q.empty())
{ now=q.front();
q.pop();
for(int i=;i<vec[now].size();i++)
{
if( --deg[ vec[now][i] ]== )
q.push(vec[now][i]);
}
}
for(int i=;i<=n;i++)//检查有没有入度不为0的结点，有的话就是环了
if(deg[i])
return false;
return true;
}bool check(int x)
{
memset(deg,,sizeof(deg));
for(int i=;i<=n;i++) vec[i].clear();
for(int i=;i<=x;i++)//建图
{
node e=edge[i];
deg[e.a]++;
vec[e.b].push_back(e.a);
}
return tuopu();
}int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=;i<=m;i++)
scanf("%d%d",&edge[i].a,&edge[i].b);
int l=,r=m;
int mid;
int ans;
while(l<=r)
{
mid=(l+r)/;
if( check(mid) )
{
ans=mid;
l=mid+;
}
else
{
r=mid-;
}
}
for(int i=;i<=m;i++)
if(i<=ans)
printf("Yes\n");
else
printf("No\n");
} return ;
}/// a b表示a是b的老板，规定箭头由b指向a，a的入度+1，a←b,b的邻接表压入a
