傳送門

題目大意：有光盤可以傳著看，問最少從哪幾個人分發，能全部傳一遍。

題解：縮點后求入度為0的點的個數

代碼：

#include<iostream> #include<cstdio> #include<cstring> #define maxn 22000 using namespace std;int n,sumedge,sumclr,top,tim,ans; int Stack[maxn],instack[maxn],low[maxn],dfn[maxn],bel[maxn],rd[maxn],head[maxn];struct Edge{int x,y,nxt;Edge(int x=0,int y=0,int nxt=0):x(x),y(y),nxt(nxt){} }edge[maxn<<1];void add(int x,int y){edge[++sumedge]=Edge(x,y,head[x]);head[x]=sumedge; }void Tarjian(int x){Stack[++top]=x;instack[x]=true;low[x]=dfn[x]=++tim;for(int i=head[x];i;i=edge[i].nxt){int v=edge[i].y;if(instack[v])low[x]=min(low[x],dfn[v]);else if(!dfn[v]){Tarjian(v);low[x]=min(low[x],low[v]);}}if(low[x]==dfn[x]){sumclr++;while(Stack[top+1]!=x){bel[Stack[top]]=sumclr;instack[Stack[top]]=false;top--;}} }int main(){scanf("%d",&n);for(int i=1;i<=n;i++){int x;while(1){scanf("%d",&x);if(!x)break;add(i,x);}}for(int i=1;i<=n;i++)if(!dfn[i])Tarjian(i);for(int x=1;x<=n;x++){for(int i=head[x];i;i=edge[i].nxt){int v=edge[i].y;if(bel[x]!=bel[v])rd[bel[v]]++;}}for(int i=1;i<=sumclr;i++)if(!rd[i])ans++;printf("%d\n",ans);return 0; } AC

?

轉載于:https://www.cnblogs.com/zzyh/p/7711631.html

總結

以上是生活随笔為你收集整理的洛谷P2835 刻录光盘的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。