数据未考虑需要画的图数量大于一的情况
查看原帖
数据未考虑需要画的图数量大于一的情况
165999
VitamineC楼主2021/5/17 20:32

考虑这个图:【□□】,显然其对应数据为 8 8 1 2 2 3 3 4 4 1 5 6 6 7 7 8 8 1,没有一个奇点,然而由于两个“□”没有连接,所以输出应为2。但按题解输出为1。这个错误出现在测试点6-11。

//这是54分代码qwq
#include<bits/stdc++.h>
using namespace std;
bool mapo[1000][1000];
bool mapin[1000][1000];
int mapl[1000],mapc=0;
bool mapflod[1000];
int n,m,floded=0;
void flod(int fr){
	mapflod[fr]=true;
	mapin[mapc][fr]=true;
	floded+=1;
	for(int i=1;i<=n;i++){
		if(mapo[fr][i]==true and mapflod[i]==false) flod(i);
	}
}
int req=0;
int main(){
	cin>>n>>m;
	int a,b;
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		mapo[a][b]=true;
		mapo[b][a]=true;
		mapl[a]+=1;
		mapl[b]+=1;
	}
	for(int i=1;i<=n;i++){
		if(mapl[i]==0) continue;
		else if(mapflod[i]==false){
			mapc+=1;
			flod(i);
		}
		if(floded==n) break;
	}
	req+=mapc;
	for(int i=1;i<=mapc;i++){
		int jic=0;
		for(int j=1;j<=n;j++){
			if(mapin[i][j] and mapl[j]%2!=0) jic++;
		}
		if(jic>2) req+=(jic-2)/2;
	}
	cout<<req;
}

2021/5/17 20:32
加载中...