首页 > 代码库 > bzoj1589[Usaco2008 Dec]Trick or Treat on the Farm 采集糖果*
bzoj1589[Usaco2008 Dec]Trick or Treat on the Farm 采集糖果*
bzoj1589[Usaco2008 Dec]Trick or Treat on the Farm 采集糖果
题意：
n个节点，每个节点有一个后继节点，问从每个节点出发能到多少个没去过的节点。n≤100000。
题解：
因为每个节点只有一个后继节点，所有tarjan缩点后就会变成一堆链，对每条链dfs一下即可。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <stack> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 100010 7 #define ll long long 8 using namespace std; 9 10 inline int read(){11 char ch=getchar(); int f=1,x=0;12 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}13 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();14 return f*x;15 }16 struct e{int f,t,n;}es[maxn]; int g[maxn],ess,n;17 void pe(int f,int t){es[++ess]=(e){f,t,g[f]}; g[f]=ess;}18 bool vis[maxn]; int bel[maxn],sm[maxn],tim,pre[maxn],low[maxn],tot,ins[maxn]; stack<int>st;19 void dfs1(int x){20 vis[x]=ins[x]=1; st.push(x); low[x]=pre[x]=++tim;21 for(int i=g[x];i;i=es[i].n)22 if(!vis[es[i].t])dfs1(es[i].t),low[x]=min(low[x],low[es[i].t]);23 else if(ins[es[i].t])low[x]=min(low[x],pre[es[i].t]);24 if(low[x]==pre[x]){25 tot++;26 while(!st.empty()){27 int now=st.top(); st.pop(); bel[now]=tot; sm[tot]++; ins[now]=0; if(now==x)break;28 }29 }30 }31 void dfs2(int x){32 for(int i=g[x];i;i=es[i].n){33 if(!vis[es[i].t])vis[es[i].t]=1,dfs2(es[i].t),sm[x]+=sm[es[i].t];else sm[x]+=sm[es[i].t];34 }35 }36 int main(){37 n=read(); inc(i,1,n){int x=read(); pe(i,x);} inc(i,1,n)if(!vis[i])dfs1(i);38 int m=ess; ess=0; memset(g,0,sizeof(g));39 inc(i,1,m)if(bel[es[i].f]!=bel[es[i].t])pe(bel[es[i].f],bel[es[i].t]);40 memset(vis,0,sizeof(vis)); inc(i,1,tot)if(!vis[i])vis[i]=1,dfs2(i);41 inc(i,1,n)printf("%d\n",sm[bel[i]]); return 0;42 }
20160923
bzoj1589[Usaco2008 Dec]Trick or Treat on the Farm 采集糖果*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。