首页 > 代码库 > 【强联通分量缩点】【搜索】bzoj2208 [Jsoi2010]连通数
【强联通分量缩点】【搜索】bzoj2208 [Jsoi2010]连通数
两次dfs缩点,然后n次dfs暴搜。
1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 using namespace std; 5 #define N 2001 6 vector<int>G[N],rG[N],vs,G2[N]; 7 typedef vector<int>::iterator ITER; 8 char s[N+1][N+1]; 9 int cmp[N],sum,cnt[N],ans,n;10 bool vis[N];11 void dfs(int U)12 {13 vis[U]=1;14 for(ITER it=G[U].begin();it!=G[U].end();it++)15 if(!vis[*it])16 dfs(*it);17 vs.push_back(U);18 }19 void dfs2(int U)20 {21 vis[U]=1;22 cmp[U]=sum;23 cnt[sum]++;24 for(ITER it=rG[U].begin();it!=rG[U].end();it++)25 if(!vis[*it])26 dfs2(*it);27 }28 void scc()29 {30 for(int i=1;i<=n;i++)31 if(!vis[i])32 dfs(i);33 memset(vis,0,sizeof(vis));34 ITER it=vs.end(); it--;35 for(;;it--)36 {37 if(!vis[*it])38 {39 sum++;40 dfs2(*it);41 }42 if(it==vs.begin()) break;43 }44 memset(vis,0,sizeof(vis));45 }46 void dfs3(int U)47 {48 vis[U]=1; ans+=cnt[U];49 for(ITER it=G2[U].begin();it!=G2[U].end();it++)50 if(!vis[*it])51 dfs3(*it);52 }53 int main()54 {55 scanf("%d",&n);56 for(int i=1;i<=n;i++)57 {58 scanf("%s",s[i]+1);59 for(int j=1;j<=n;j++)60 if(s[i][j]==‘1‘)61 {62 G[i].push_back(j);63 G[j].push_back(i);64 }65 }66 scc();67 for(int i=1;i<=n;i++)68 for(int j=1;j<=n;j++)69 if(s[i][j]==‘1‘&&cmp[i]!=cmp[j])70 G2[cmp[i]].push_back(cmp[j]);71 for(int i=1;i<=sum;i++)72 {73 memset(vis,0,sizeof(vis));74 dfs3(i);75 }76 printf("%d\n",ans);77 return 0;78 }
【强联通分量缩点】【搜索】bzoj2208 [Jsoi2010]连通数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。