hdu 5413 CRB and Roads(拓扑排序+bitset)
题意：
给你一个n个点的有向无环图，定义重复边为 对于一条边u->v，如果去掉这条边，u还是等到达v，则u->v是重复边。
问有多少条重复边。
题解：
显然有向无环图，先拓扑排序一下，这样排在前面的节点可能到达后面的节点，我们再将边的关系按照拓扑排序的结果排序，然后从后往前拓展。这样做就能将关系传递给上一个节点。
比如样例排完后是1，2，3，4，5。
现在从5开始找，发现没有可到达的节点，4同理。然后到3，发现3可以到4，然后4能到达的3也能到达，然后这里用bitset记录一下。然后到2，发现可以到4，5，然后标记一下。最后是1，发现1可以到2，然后将2能到底的点传递给1，然后发现1还可以到3，将3能到底的点传递给1，然后发现1还可以到4，此时4已经是1可以到达的点了，所以这条边可以去掉，ans++,5同理。
1 #include<bits/stdc++.h> 2 #define mst(a,b) memset(a,b,sizeof(a)) 3 #define F(i,a,b) for(int i=(a);i<=(b);++i) 4 using namespace std; 5 6 const int N=2e4+7; 7 int t,n,m,in[N],Q[N],ans,hd,tl,h[N]; 8 vector<int>G[N]; 9 bitset<N>bs[N]; 10 11 bool cmp(int a,int b){return h[a]<h[b];} 12 13 int main(){ 14 scanf("%d",&t); 15 while(t--) 16 { 17 scanf("%d%d",&n,&m); 18 F(i,1,n)G[i].clear(),bs[i].reset(),in[i]=0; 19 F(i,1,m) 20 { 21 int x,y; 22 scanf("%d%d",&x,&y); 23 G[x].push_back(y),in[y]++; 24 } 25 hd=1,tl=0,ans=0; 26 F(i,1,n)if(in[i]==0)Q[++tl]=i,h[i]=tl; 27 while(hd<=tl)for(int x=Q[hd++],i=0;i<G[x].size();i++) 28 if(!--in[G[x][i]])Q[++tl]=G[x][i],h[G[x][i]]=tl; 29 for(int i=tl;i;i--) 30 { 31 sort(G[Q[i]].begin(),G[Q[i]].end(),cmp); 32 for(int &it:G[Q[i]]) 33 { 34 if(bs[Q[i]][it])ans++; 35 bs[Q[i]]|=bs[it]; 36 bs[Q[i]][it]=1; 37 } 38 } 39 printf("%d\n",ans); 40 } 41 return 0; 42 }View Code 优质内容筛选与推荐>>
1、Git常用命令
2、监控调优工具详细参数整理
3、Android基础TOP5_1：AutoCompleteTextView自动补全文本框
4、EA经典入门教程
5、Django 错误 cannot import name