首页 > 代码库 > 【bzoj2208】[Jsoi2010]连通数

【bzoj2208】[Jsoi2010]连通数

2024-08-16 05:03:20   221人阅读

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.
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 #include<ctime> 7 #include<algorithm> 8 using namespace std; 9 #define MAXN 1001010 struct node{int y,next;}e[4000010],e2[4000010];11 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[2010][2010];12 char ch[MAXN];13 long long ans;14 void insert(int x,int y) {e[++len].next=Link[x];Link[x]=len;e[len].y=y;}15 void insert2(int x,int y) {e2[++len].next=Link2[x];Link2[x]=len;e2[len].y=y;}16 void tarjan(int x)17 {18     dfn[x]=low[x]=++now;19     stack[++top]=x;  instack[x]=1;20     for(int i=Link[x];i;i=e[i].next)21     {22         if(!dfn[e[i].y]){tarjan(e[i].y);  low[x]=min(low[x],low[e[i].y]);}23         else if(instack[e[i].y])  low[x]=min(low[x],dfn[e[i].y]);24     }25     if(dfn[x]==low[x])26     {27         int y;  bcnt++;28         do{y=stack[top--];instack[y]=0;belong[y]=bcnt;size[bcnt]++;}while(x!=y);29     }30 }31 void build()32 {33     len=0;34     for(int i=1;i<=n;i++)35         for(int j=Link[i];j;j=e[j].next)36             if(belong[i]!=belong[e[j].y]&&!map[belong[i]][belong[e[j].y]])  37             {38                 insert2(belong[i],belong[e[j].y]); 39                 map[belong[i]][belong[e[j].y]]=1;40             }41 }42 void dfs(int x)43 {44     vis[x]=1;  ans+=size[x];45     for(int i=Link2[x];i;i=e2[i].next)46         if(!vis[e2[i].y])  dfs(e2[i].y);47 }48 int main()49 {50     //freopen("cin.in","r",stdin);51     //freopen("cout.out","w",stdout);52     scanf("%d",&n);53     for(int i=1;i<=n;i++)54     {55         scanf("%s",ch+1);56         for(int j=1;j<=n;j++)  if(ch[j]==‘1‘)  insert(i,j);57     }58     for(int i=1;i<=n;i++)  if(!dfn[i])  tarjan(i);59     build();60     for(int i=1;i<=n;i++)  61     {62         memset(vis,0,sizeof(vis));63         dfs(belong[i]);64     }65     printf("%lld\n",ans);66     return 0;67 }

 

【bzoj2208】[Jsoi2010]连通数


联系
我们