BZOJ 2208[Jsoi2010]连通数

 ?1 #include <iostream> ?2 #include <stdio.h> ?3 #include <string.h> ?4 #include <algorithm> ?5 using namespace std; ?6 #define maxm 2002 ?7 #define maxn 2000001 ?8 struct edge ?9 { 10 ????int u,v,nex; 11 }e[maxn]; 12 int pr[maxm],cnt; 13 int CNT; 14 inline void add(int u,int v) 15 { 16 ????e[++cnt]=(edge){u,v,pr[u]}; 17 ????pr[u]=cnt; 18 } 19 inline void ADD(int u,int v) 20 { 21 ????e[++CNT]=(edge){u,v,pr[u]}; 22 ????pr[u]=CNT; 23 } 24 int n; 25 char s[maxm]; 26 int dfn[maxm],scc_cnt,scc_dfn,scc_size[maxm],belong[maxm],low[maxm]; 27 int st[maxm],top; 28 bool vis[maxm]; 29 void tarjan(int u) 30 { 31 ????vis[u]=true; 32 ????dfn[u]=low[u]=++scc_dfn; 33 ????st[++top]=u; 34 ????int v; 35 ????for(int i=pr[u];i;i=e[i].nex) 36 ????{ 37 ????????v=e[i].v; 38 ????????if(!dfn[v]) 39 ????????{ 40 ????????????tarjan(v); 41 ????????????low[u]=min(low[u],low[v]); 42 ????????} 43 ????????else 44 ????????????if(vis[v]) 45 ????????????????low[u]=min(low[u],dfn[v]); 46 ????} 47 ????if(dfn[u]==low[u]) 48 ????{ 49 ????????int v=-1; 50 ????????++scc_cnt; 51 ????????while(v!=u) 52 ????????{ 53 ????????????v=st[top--]; 54 ????????????vis[v]=false; 55 ????????????belong[v]=scc_cnt; 56 ????????????++scc_size[scc_cnt]; 57 ????????} 58 ????} 59 } 60 void init() 61 { 62 ????for(int i=1;i<=n;i++) 63 ????????if(!dfn[i]) 64 ????????????tarjan(i); 65 ????memset(pr,0,sizeof(pr)); 66 ????for(int i=1;i<=cnt;i++) 67 ????????if(belong[e[i].u]!=belong[e[i].v]) 68 ????????????ADD(belong[e[i].u],belong[e[i].v]); 69 } 70 int ans; 71 void dfs(int u) 72 { 73 ????int v; 74 ????ans+=scc_size[u]; 75 ????vis[u]=true; 76 ????for(int i=pr[u];i;i=e[i].nex) 77 ????{ 78 ????????v=e[i].v; 79 ????????if(!vis[v]) 80 ????????????dfs(v); 81 ????} 82 } 83 int main() 84 { 85 ????scanf("%d",&n); 86 ????for(int i=1;i<=n;i++) 87 ????{ 88 ????????scanf("%s",s); 89 ????????for(int j=0;j<n;j++) 90 ????????????if(s[j]==‘1‘) 91 ????????????????add(i,j+1); 92 ????} 93 ????init(); 94 ????int tot=0; 95 ????for(int i=1;i<=scc_cnt;i++) 96 ????{ 97 ????????memset(vis,0,sizeof(vis)); 98 ????????ans=0; 99 ????????dfs(i);100 ????????tot+=ans*scc_size[i];101 ????}102 ????printf("%d",tot);103 }