本质是在求无向,无环联通图的个数
证明:对于每一个连通图,它们之间没有边,互相没有影响
只要一个连通图中存在一个环,那么将环中的所有边都指向一个时针方向,就构成了一棵基环树–有至少一个环,环中的每一个点都延伸出一棵树(或者又形成一棵子基环树)不难证出存在一种方案,使所有点的入度均不为0
而无环的无向连通图是一棵树,n个顶点共有n-1条边,则必然会有一个点成为根节点,
该根节点没有入度
故结论:若一个连通图中没有环,则至少会有一个孤立点,贡献为1,;若存在环,则可以使其没有孤立点,贡献可为0
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n,m,flag;//flag表示一块连通图内是不是有环
int h[100010],e[200010],ne[200010],idx;
bool st[100010];
void add(int a,int b)
{
e[idx]=b; ne[idx]=h[a]; h[a]=idx++;
}
bool dfs(int u,int fa)
{
st[u]=true;
for(int i=h[u];i!=-1;i=ne[i])
{
int v=e[i];
if(v==fa) continue;
if(st[v])
{
flag=false;
continue;//有环,则标记,并跳过,否则可能在环内转圈
}
dfs(v,u);
}
}
int main()
{
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(!st[i])
{
flag=true;
dfs(i,-1);//遍历连通图
if(flag) ans++;//统计一个无环的连通图的数量
}
}
cout<<ans;
return 0;
}
算法2
(并查集)
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n,m;
int fa[100010];//fa[i]为并查集,表示i的祖先
bool st[100010];//st[i]=true表示点i已经在一个无向连通图中
//则fa[i]==i&&!st[i]表示存在一个无向无环联通图
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
//每一个集合都是一个无向连通图,
//判断无向连通图的数量时,看fa[i]==i的点的个数i即可
//在判断每一个图中有没有环:在建立每一条边(即将a与b归为同一集合)之前,先判断a,b是否已在同一集合中,
//若已在(即find(a)==find(b)),则一定存在环
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
while(m--)
{
int x,y;
cin>>x>>y;
int a=find(x),b=find(y);
if(a==b)//该图为无向联通图,应做上标记
{
st[a]=true;
}
else//归为一个集合
{
fa[a]=b;
st[b]|=st[a];
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(fa[i]==i&&!st[i]) ans++;
}
cout<<ans;
return 0;
}