网站开发前端要学什么/营销网站定制公司

题意

给出$n$个顶点和$m$条边，求这个图中环的个数

思路

利用并查集的性质，环上的顶点都在同一个集合中
在输入的时候记录下来每个顶点的度数，查找两个点相连，且度数均为$2$的点，如果这两个点的父节点相同，表示这两个点在一个环中，环的个数$+1$

AC代码

/*************************************************************************> File Name: E.cpp> Author: WZY> QQ: 2697097900> Created Time: 2018年12月09日 星期日 17时07分25秒************************************************************************/#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
#define pi acos(-1.0)
#define INF 0x7f7f7f7f
const double E=exp(1);
const int maxn=1e6+10;
const int mod=1e9+7;
using namespace std;
int ans;
int f[maxn];
int u[maxn];
int v[maxn];
int vis[maxn];
int find(int x)
{if(f[x]==x)return x;elsereturn f[x]=find(f[x]);
}
int join(int x,int y)
{int dx=find(x);int dy=find(y);cout<<"====="<<x<<"  "<<y<<endl;cout<<dx<<"      "<<dy<<endl;if(dx!=dy)f[dx]=dy;elseans++;
}
int main(int argc, char const *argv[])
{ios::sync_with_stdio(false);int n,m;cin>>n>>m;for(int i=1;i<=n;i++)f[i]=i;for(int i=0;i<m;i++){cin>>u[i]>>v[i];vis[u[i]]++;vis[v[i]]++;}for(int i=0;i<m;i++){if(vis[u[i]]==2&&vis[v[i]]==2)join(u[i],v[i]);}cout<<ans<<endl;return 0;
}