C++14(g++5.4) 解法, 执行用时: 55ms, 内存消耗: 6756K, 提交时间: 2019-12-21 13:01:32

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,vis[N];
int du[N],tot;
vector<int>G[N];
void dfs(int u)
{
    tot++;
    vis[u]=1;
    du[G[u].size()]++;
    for(int v:G[u]){
        if(vis[v]) continue;
        dfs(v);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    ll ans=0;
    int f=1;
    for(int i=1;i<=n&&f;++i){
        if(vis[i]) continue;
        tot=0;
        du[1]=du[2]=0;
        dfs(i);
        if(du[1]==2&&du[2]==tot-2) ans+=0;
        else if(du[1]==0&&du[2]==tot) ans+=tot;
        else if(du[1]==tot-1) ans+=tot-1;
        else f=0;
    }
    if(!f) puts("-1");
    else printf("%lld\n",ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 100ms, 内存消耗: 6876K, 提交时间: 2019-12-21 13:08:57

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;

int n,m,ma,mi,cnt,cc;
int in[maxn];
bool vis[maxn];
vector<int> v[maxn];

void dfs( int u )
{
	vis[u]=true;
	mi = min(mi,in[u]);
	ma = max(ma,in[u]);
	cnt++;
	cc += v[u].size();
	for( auto p:v[u] )
	{
		if( vis[p] ) continue;
		dfs(p);
	}
}

int main()
{
	int a,b;
	scanf("%d%d",&n,&m);
	for( int i=0;i<m;i++ )
	{
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
		in[a]++;in[b]++;
	}
	int ans=0;
	bool flag = true;
	for( int i=1;i<=n;i++ )
	{
		if( vis[i] ) continue;
		ma=0;mi=1e9;cnt=0;cc=0;
		dfs(i);
		if( ma==3 && cc==6 && mi==1 && cnt==4 ) ans+=3; // 四点菊花图 
		else if( ma>2 ) flag=false;
		else if( mi==2 ) ans+=cnt; // 环 
	}
	if( !flag ) ans=-1;
	printf("%d\n",ans);
}