C++14(g++5.4) 解法, 执行用时: 54ms, 内存消耗: 6264K, 提交时间: 2020-05-21 14:52:39

#include<bits/stdc++.h>
using namespace std;
 
vector<int>R[100005];
bool F=0,V[100005]={0},S[100005];
void DFS(int x)
{
    int i,j;
    for(i=0;i<R[x].size();i++)
    {
        j=R[x][i];
        if(!V[j])V[j]=1,S[j]=!S[x],DFS(j);
        else if(S[x]==S[j])F=1;
    }
}
int main()
{
    int i,j,ans=0,n,m;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&i,&j);
        R[i].push_back(j),R[j].push_back(i);
    }
    for(i=1;i<=n;i++)if(!V[i])ans++,V[i]=S[i]=1,DFS(i);
    printf("%d\n",ans-F);
}

Python3 解法, 执行用时: 492ms, 内存消耗: 19712K, 提交时间: 2021-06-07 17:58:26

from collections import deque

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
	u, v = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)

vi, q, cnt, found = [-1] * n, deque(), 0, False
for s in range(n):
	if vi[s] >= 0: continue
	cnt += 1
	vi[s] = 0
	q.append(s)
	while q:
		u = q.popleft()
		for v in g[u]:
			if vi[v] < 0:
				vi[v] = vi[u] + 1
				q.append(v)
			else:
				if abs(vi[v] - vi[u]) % 2 == 0: found = True

print(cnt - 1 + (0 if found else 1))

C++(g++ 7.5.0) 解法, 执行用时: 72ms, 内存消耗: 7164K, 提交时间: 2022-11-09 21:08:31

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

vector<int>R[100005];
bool F=0,V[100005]={0},S[100005];
void DFS(int x)
{
	int i,j;
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		if(!V[j])V[j]=1,S[j]=!S[x],DFS(j);
		else if(S[x]==S[j])F=1;
	}
}
int main()
{
	int i,j,ans=0,n,m;
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&i,&j);
		R[i].push_back(j),R[j].push_back(i);
	}
	for(i=1;i<=n;i++)if(!V[i])ans++,V[i]=S[i]=1,DFS(i);
	printf("%d\n",ans-F);
}

C++11(clang++ 3.9) 解法, 执行用时: 48ms, 内存消耗: 5860K, 提交时间: 2020-02-27 01:39:26

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

vector<int>R[100005];
bool F=0,V[100005]={0},S[100005];
void DFS(int x)
{
	int i,j;
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		if(!V[j])V[j]=1,S[j]=!S[x],DFS(j);
		else if(S[x]==S[j])F=1;
	}
}
int main()
{
	int i,j,ans=0,n,m;
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%d%d",&i,&j);
		R[i].push_back(j),R[j].push_back(i);
	}
	for(i=1;i<=n;i++)if(!V[i])ans++,V[i]=S[i]=1,DFS(i);
	printf("%d\n",ans-F);
}