MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
有个介绍,以前些的,这里贴个乱乱的代码,有错误请指正

有分量了后,缩点就好弄了,硬搞就可以

矩阵存储 :
#include <stdio.h>
#include 
<string.h>
int map[100][100], mapt[100][100], n, m, ans, f[100], s[100], time;
bool judge[100];
void dfs(int v){//正图dfs
    int i;judge[v] = true;
    
for(i = 1; i <= n; i++){
        
if(map[v][i] && !judge[i]){
            dfs(i);
        }
    }
    f[v] 
= ++time;
}

void dfst(int v){//反图dfs
    int i; judge[v] = true;
    
for(i = 1; i <= n; i++){
        
if(mapt[v][i] && !judge[i]){
            dfst(i);
        }
    }
}

int main(){
    freopen(
"strong.in""r", stdin);
    freopen(
"strong.out""w", stdout);
    
int i, j, u, v;
    
while(scanf("%d%d"&n, &m) != -1){
        memset(map, 
0sizeof(map));
        memset(mapt, 
0sizeof(mapt));
        memset(f, 
0sizeof(f));
        time 
= ans = 0;
        
for(i = 0; i < m; i++){
            scanf(
"%d%d"&u, &v);
            map[u][v] 
= true;
            mapt[v][u] 
= true;
        }
        
for(i = 1; i <= n; i++)if(!judge[i])dfs(i);
        memset(judge, 
0sizeof(judge));
        
for(i = 1; i <= n; i++)s[f[i]] = i;//按照拓扑序列dfs倒置矩阵
        for(i = n; i >= 1; i--){
            
if(!judge[s[i]]){
                dfst(s[i]);
                ans
++;//倒置矩阵的连同分量个数就是结果了。
            }
        }
        printf(
"storng num = %d\n", ans);
    }
    
return 0;
}
链表存储 :
#include <stdio.h>
#include 
<string.h>
struct e{
    
int v;
    e
* next;
};

e
* map[100], *mapt[100], edge[1000], edget[1000];
int m, n, el, etl, ans, f[100], s[100], time;
bool judge[100];

void dfs(int v){
    
int i, t;e* l = map[v]; 
    judge[v] 
= true;
    
while(l){
        t 
= l->v;
        
if(!judge[t])dfs(t);
        l 
= l->next;
    }f[v] 
= ++time;
}

void dfst(int v){
    
int i, t; e* l = mapt[v];
    judge[v] 
= true;
    
while(l){
        t 
= l->v;
        
if(!judge[t])dfst(t);
        l 
= l->next;
    }
}

int main(){
    freopen(
"strong_link.in""r", stdin);
    freopen(
"strong_link.out""w", stdout);
    
int i, j, u, v;
    
while(scanf("%d%d"&n, &m) != -1){
        memset(map, 
0sizeof(map));
        memset(mapt, 
0sizeof(mapt));
        memset(f, 
0sizeof(f));
        memset(s, 
0sizeof(s));
        el 
= ans = etl = time = 0;
        
for(i = 0; i < m; i++){
            scanf(
"%d%d"&u, &v);
            edge[el].v 
= v;
            edge[el].next 
= map[u];
            map[u] 
= &edge[el++];
            edget[etl].v 
= u;
            edget[etl].next 
= mapt[v];
            mapt[v] 
= &edget[etl++];
        }
        
for(i = 1; i <= n; i++)if(!judge[i])dfs(i);
        
for(i = 1; i <= n; i++)s[f[i]] = i;
        memset(judge, 
0sizeof(judge));
        
for(i = n; i >= 1; i--){
            
if(!judge[s[i]]){
                dfst(s[i]);
                ans
++;
            }
        }
        printf(
"strong num = %d\n", ans);
    }
    
return 0;
}


posted on 2009-10-06 23:28 memorygarden 阅读(334) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理