【bzoj2208】[Jsoi2010]连通数

2208: [Jsoi2010]连通数

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 2305  Solved: 989
[Submit][Status][Discuss]

Description

Input

输入数据第一行是图顶点的数量，一个正整数N。 接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。

Output

输出一行一个整数，表示该图的连通数。

Sample Input

3
010
001
100

Sample Output

9

 

 

 

【题解】

我用的暴力，A掉了。。。

首先tarjan缩点，然后再新图上dfs就行了。

写的时候脑子瓦特了，把a[j].y直接写成了j.

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<ctime>

 #include<algorithm>

 using namespace std;

 #define MAXN 10010

 struct node{int y,next;}e[],e2[];

 int n,len,now,top,bcnt,Link[MAXN],Link2[MAXN],vis[MAXN],belong[MAXN],size[MAXN],dfn[MAXN],low[MAXN],stack[MAXN],instack[MAXN],map[][];

 char ch[MAXN];

 long long ans;

 void insert(int x,int y) {e[++len].next=Link[x];Link[x]=len;e[len].y=y;}

 void insert2(int x,int y) {e2[++len].next=Link2[x];Link2[x]=len;e2[len].y=y;}

 void tarjan(int x)

 {

     dfn[x]=low[x]=++now;

     stack[++top]=x;  instack[x]=;

     for(int i=Link[x];i;i=e[i].next)

     {

         if(!dfn[e[i].y]){tarjan(e[i].y);  low[x]=min(low[x],low[e[i].y]);}

         else if(instack[e[i].y])  low[x]=min(low[x],dfn[e[i].y]);

     }

     if(dfn[x]==low[x])

     {

         int y;  bcnt++;

         do{y=stack[top--];instack[y]=;belong[y]=bcnt;size[bcnt]++;}while(x!=y);

     }

 }

 void build()

 {

     len=;

     for(int i=;i<=n;i++)

         for(int j=Link[i];j;j=e[j].next)

             if(belong[i]!=belong[e[j].y]&&!map[belong[i]][belong[e[j].y]])

             {

                 insert2(belong[i],belong[e[j].y]);

                 map[belong[i]][belong[e[j].y]]=;

             }

 }

 void dfs(int x)

 {

     vis[x]=;  ans+=size[x];

     for(int i=Link2[x];i;i=e2[i].next)

         if(!vis[e2[i].y])  dfs(e2[i].y);

 }

 int main()

 {

     //freopen("cin.in","r",stdin);

     //freopen("cout.out","w",stdout);

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         scanf("%s",ch+);

         for(int j=;j<=n;j++)  if(ch[j]=='')  insert(i,j);

     }

     for(int i=;i<=n;i++)  if(!dfn[i])  tarjan(i);

     build();

     for(int i=;i<=n;i++)

     {

         memset(vis,,sizeof(vis));

         dfs(belong[i]);

     }

     printf("%lld\n",ans);

     return ;

 }