設(shè)無向圖頂點個數(shù)為n，邊數(shù)為m。DFS遍歷無向圖，找到該無向圖連通分量的個數(shù)num，則冗余關(guān)系數(shù)為m-n+num。另外由于此題中頂點數(shù)較多而邊數(shù)較少，采用鄰接表存儲，提高效率。
以下是我的代碼：
#include<iostream>
#include<string.h>
#define maxn 1007
#define maxm 1007
using namespace std;
typedef struct
{
long v,w;
}edge;
long n,m,num;
long cnt,first[maxn],next[2*maxm];
edge e[2*maxm];
bool used[maxn];
void dfs(long s)
{
used[s]=true;
for(long i=first[s];i;i=next[i])
if(!used[e[i].v])
dfs(e[i].v);
}
int main()
{
memset(first,0,sizeof(first));
memset(next,0,sizeof(next));
memset(e,0,sizeof(e));
cin>>m>>n;
cnt=0;
for(long i=1;i<=m;i++)
{
long a,b;
cin>>a>>b;
cnt++;e[cnt].v=b;
next[cnt]=first[a];
first[a]=cnt;
cnt++;e[cnt].v=a;
next[cnt]=first[b];
first[b]=cnt;
}
// Input
num=0;
memset(used,false,sizeof(used));
for(long i=1;i<=n;i++)
if(!used[i])
{
num++;
dfs(i);
}
// DFS
cout<<m-n+num<<endl;
// Output
return 0;
}
posted on 2010-10-18 15:38
lee1r 閱讀(304)
評論(1) 編輯 收藏 引用 所屬分類:
題目分類：圖論