【强联通分量缩点】【搜索】bzoj2208 [Jsoi2010]连通数

 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 }