设无向图顶点个数为n，边数为m。DFS遍历无向图，找到该无向图连通分量的个数num，则冗余关系数为m-n+num。另外由于此题中顶点数较多而边数较少，采用邻接表存储，提高效率。
以下是我的代码：
#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 阅读(300)
评论(1) 编辑 收藏 引用 所属分类:
题目分类：图论