\[Problem \]
有 \(N\) 个机器人,给出 \(M\) 组关系,表示两个机器人的能力关系,问至少需要前几组关系可以确定所有机器人的排名。
\[Solution \]由于是求最少的前几组关系,而关系越少越难确定排名,关系越多越容易确定,不难发现本题满足单调性,考虑二分。
那么给出关系要求总排名的题,就应该使用拓扑排序实现。
\[Topological\ Sorting \]对于一个有向图,每次从一个入度为 \(0\) 的节点开始,删除它和它的所有出边,并将它存储到拓扑序列里。
如果图存在环,或者关系不足,那么拓扑排序将无法遍历所有节点(但是本题不考虑环,因为机器人的能力不可能成为一个环)。
剩下的拓扑序列就是机器人的总排名。
\[Code \]#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int x[100005],y[100005],d[100005];
queue<int>q;
namespace Graph //链式前向星存图
{
int h[100005],to[100005],nxt[100005],idx;
void init_graph(void)
{
while(!q.empty())
q.pop();
memset(d,0,sizeof(d));
memset(h,-1,sizeof(h));
idx=0;
}
void add_edge(int u,int v)
{
to[idx]=v;
nxt[idx]=h[u];
h[u]=idx++;
}
}
using namespace Graph;
bool check(int k)
{
init_graph();
for(int i=1;i<=k;i++)
{
add_edge(x[i],y[i]);
d[y[i]]++;//存每个点的入度
}
for(int i=1;i<=n;i++)
if(d[i]==0)q.push(i);
if(q.size()>1||q.size()==0)return false;
while(!q.empty())//用 BFS 遍历
{
int t=q.front();
q.pop();
for(int i=h[t];i!=-1;i=nxt[i])
{
int j=to[i];
d[j]--;//删边
if(!d[j])//入度为 0
q.push(j);
}
if(q.size()>1)return false;
}
return true;
}
signed main(void)
{
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>x[i]>>y[i];
int l=1,r=m,mid;
while(l<r)//二分
{
mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
if(check(l))
cout<<l;
else
cout<<-1;
return 0;
}
标签:Rapping,idx,int,题解,void,机器人,CF645D,mid,100005
From: https://www.cnblogs.com/dijkstraphoenix/p/18382982