| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 498 人关注过本帖, 1 人收藏
标题:强连通分量
只看楼主 加入收藏
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
结帖率:79.37%
收藏(1)
已结贴  问题点数:20 回复次数:4 
强连通分量
题目:http://oj.
我写了强连通分量,样例过了,但是还是好像有问题,请各位高手帮我看看
代码:
#include <stdio.h>
#include <stdlib.h>
int count=0;
void sort1(int t,int n,int mark[],int sign[],long map[100][100])
{
    int i;
    mark[t]=1;
    for(i=0;i<n;i++)
    if(map[t][i]==0&&mark[i]==0)
    sort1(i,n,mark,sign,map);
    sign[count++]=t;
}
void sort2(int t,int n,int mark[],int sign[],long map[100][100])
{
    int i;
    mark[t]=1;
    for(i=0;i<n;i++)
    if(map[i][t]==0&&mark[i]==0)
    sort2(i,n,mark,sign,map);
}
int strong_connected(long map[100][100],int n)
{
    int mark[100]={0},sign[100]={0};
    int i,ans=0;
    for(i=0;i<n;i++)
    if(mark[i]==0)
    sort1(i,n,mark,sign,map);
    memset(mark,0,sizeof(mark));
    for(i=n-1;i>=0;i--)
    if(mark[sign[i]]==0)
    {
    ans++;
    sort2(sign[i],n,mark,sign,map);
    }
    return ans;
}
int main()
{
long map[100][100];
int m,n,i,ans=0;
int start,end;
scanf("%d %d",&n,&m);
for(i=0;i<m;i++)
{
scanf("%d %d",&start,&end);
map[start-1][end-1]=1;
}
ans=strong_connected(map,n);
printf("%d\n",ans);
system("pause");
return 0;
}

[ 本帖最后由 sunyh1999 于 2011-4-9 19:12 编辑 ]
搜索更多相关主题的帖子: count void include 
2011-04-09 12:41
shinan77
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:87
专家分:188
注 册:2010-9-24
收藏
得分:7 
memset(mark,0,sizeof(mark));是什么东东?

--------将学到的东西为我所用,这才是学习的目的 --------
2011-04-09 13:07
hnuhsg1226
Rank: 9Rank: 9Rank: 9
来 自:中国
等 级:蜘蛛侠
威 望:2
帖 子:314
专家分:1314
注 册:2011-3-27
收藏
得分:7 
数组mark全置0

我的地盘
2011-04-09 13:09
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 

欢迎来到我的博客:http://blog..cn/noisunyuhong
2011-04-10 08:13
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:7 
memset(mark,0,sizeof(mark));是什么东东?   

初始化内存数据  也就是把mark所指向的sizeof(mark)大小的内存初始化为0

                                         
===========深入<----------------->浅出============
2011-04-10 10:14
快速回复:强连通分量
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.048360 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved