글 읽기 - 어디가 틀렸는지 모르겠어요... 도와주세요

tnswoekd 7년 전 0

홀수의 개수가 0개인 그래프와 0개인 그래프를 이으면 홀수의 개수가 2개인 그래프가 나오고

홀수의 개수가 0개인 그래프와 n개 이상인 그래프를 이으면 홀수의 개수가 n개인 그래프가 나오고

홀수의 개수가 n개인 그래프와 m개인 그래프를 이으면 홀수의 개수가 n+m-2개인 그래프가 나오고...

이런 방식으로 접근했는데 오류가 있는지 모르겠어요...

#include <iostream>
#include <stdio.h>
#include <vector>
#include <list>
#include <map>

using namespace std;

int *parent;
map<int, int> i_graph;
map<int, int>::iterator mit;
list<int> oddchk;
vector<list<int > > graph;
list<int>::iterator lit;

int find(int a){
	if(a==parent[a]) return a;
	return parent[a]=find(parent[a]);
}

void insert(int a, int b){
	int p1=find(a);
	int p2=find(b);
	if(p1>p2) parent[p1]=p2;
	else parent[p2]=p1;
}

void compress(int n){
	int temp;
	for(int i=1;i<=n;i++){
		temp=find(i);
		mit=i_graph.find(temp);
		if(mit==i_graph.end()){
			if(graph[i].size() & 1)
				i_graph.insert(make_pair(temp, 1));
			else
				i_graph.insert(make_pair(temp, 0));
			
			continue;
		}
		if(graph[i].size() & 1)
			mit->second++;
	}

	for(mit=i_graph.begin();mit!=i_graph.end();++mit){
		oddchk.push_back(mit->second);
		//printf("%d\n", mit->second);
	}
}

int main(){

	int n, m, v1, v2, count=0;
	scanf("%d %d", &n, &m);

	graph.resize(n+1);
	parent=new int[n+1];

	for(int i=0;i<=n;i++) parent[i]=i;

	for(int i=0;i<m;i++){
		scanf("%d %d", &v1, &v2);
		graph[v1].push_back(v2);
		graph[v2].push_back(v1);		
		insert(v1, v2);
	}

	compress(n);

	while(1){
		if(oddchk.size()>1){
			v1=oddchk.front(); oddchk.pop_front();
			if(v1==0){
				if(oddchk.front()==0) oddchk.front()=2;
			}else{
				if(oddchk.front()==0)
					oddchk.front()=v1;
				else
					oddchk.front()+=v1-2;
			}
		}else{
			if(oddchk.front()<=2) 
				break;
			
			oddchk.front()-=2;
		}
		count++;
	}
	printf("%d", count);

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀렸는지 모르겠어요... 도와주세요

tnswoekd 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말