2208. [JSOI2010]连通数【Tarjan】

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #define N (2000+10) 5 using namespace std; 6 struct node 7 { 8 ????int to,next; 9 }edge[N*N*2];10 int Dfn[N],dfs_num,Color[N],col_num;11 int vis[N],stack[N],top,Low[N];12 int n,ans,head[N],num_edge;13 char s[N];14 15 void add(int u,int v)16 {17 ????edge[++num_edge].to=v;18 ????edge[num_edge].next=head[u];19 ????head[u]=num_edge;20 }21 22 void Tarjan(int x)23 {24 ????Dfn[x]=Low[x]=++dfs_num;25 ????vis[x]=true;26 ????stack[++top]=x;27 ????for (int i=head[x];i;i=edge[i].next)28 ????????if (!Dfn[edge[i].to])29 ????????{30 ????????????Tarjan(edge[i].to);31 ????????????Low[x]=min(Low[x],Low[edge[i].to]);32 ????????}33 ????????else34 ????????????if (vis[edge[i].to])35 ????????????????Low[x]=min(Low[x],Dfn[edge[i].to]);36 ????if (Dfn[x]==Low[x])37 ????{38 ????????vis[x]=false;39 ????????Color[x]=++col_num;40 ????????while (stack[top]!=x)41 ????????{42 ????????????vis[stack[top]]=false;43 ????????????Color[stack[top--]]=col_num;44 ????????}45 ????????top--;46 ????}47 }48 49 50 int main()51 {52 ????scanf("%d",&n);53 ????for (int i=1;i<=n;++i)54 ????{55 ????????scanf("%s",s);56 ????????for (int j=1;j<=n;++j)57 ????????????if (s[j-1]==‘1‘)58 ????????????????add(i,j);59 ????}60 ????for (int i=1;i<=n;++i)61 ????????if (!Dfn[i])62 ????????????Tarjan(i);63 ????for (int i=1;i<=n;++i)64 ????????for (int j=1;j<=n;++j)65 ????????????if (Color[i]==Color[j])66 ????????????????++ans;67 ????printf("%d",ans);68 }