글 읽기 - 맞았습니다 나올것가태!!!! 맞았습니다 나올것가태!!!!

surung9898 3년 전 0

그러기 위해서는 선생님들의 도움이 절실합니다....

논리는 다음과 같습니다. n개의 정점에 n개의 간선을 가지므로 반드시 1개의 사이클이 형성될 것이라고 생각했습니다.

따라서 사이클을 먼저 찾은 뒤, 이 사이클 각각에 번호를 붙입니다.

이 때 사이클에 번호를 붙이는 순서는 시계 방향 또는 시계 반대방향입니다. 따라서, 만약 정점 갯수가 2n개인 사이클에서 a + n = b일때 a와 b는 정반대에 있고, 이 a와 b 사이의 simple path는 2개라고 생각했습니다.

이 후 사이클의 각 정점 i와 연결된 subtree의 모든 정점에 대해 번호 i를 할당한 후, 각각의 쿼리에 대하여

1. 사이클의 정점 갯수가 홀수라면 반드시 1을 출력

2. 사이클의 정점 갯수가 짝수라면, 이 정점에 할당된 값 x와 y가 x + n = y 관계를 가진다면 2, 아니면 1을 출력하도록 하였습니다.

그러나 어림도 없지 틀렸습니다... 반례나, 틀린 점 지적해주시면 감사하겠습니다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <functional>
#include <math.h>
#include <time.h>
#include <fstream>
#include <list>
#include <climits>
#include <iomanip>

using namespace std;

typedef long long int lld;
typedef long double ld;
typedef vector<int> vi;
typedef vector<char> vch;
typedef vector<lld> vlld;
typedef vector<vi> vivi;
typedef vector<vlld> vlvl;
typedef vector<vch> vcvc;

vivi tree;
vi visit, cycle;
int check = 0, checknorm = 0, check_cycle = 0, cycle_cnt = 0;
//tree: 트리, visit: 방문 했는지 여부, cycle: (함수 'dfs' 결과) 사이클일 시 번호 할당, 아닐 시 0 / (함수 'dfs2' 결과) 모든 정점에 할당된 번호
//check: 사이클을 찾았을 시의 flag, checknorm: 사이클을 처음 찾았을 때의 정점 값
//check_cycle: 할당하는 번호, cycle_cnt: 사이클에 속하는 정점 갯수

void dfs(int st, int trail, int no) //사이클을 찾는 dfs. st: 현재 위치, trail: 직전 위치, no: 0이면 사이클 아니라고 생각, 1이면 사이클
{
	int tmp;

	for (int i = 0; i < (int)tree[st].size(); ++i)
	{
		tmp = tree[st][i];

		if (visit[tmp] == 0) //방문한 적 없음
		{
			visit[tmp] = 1;

			if (check) //사이클 flag ON
				dfs(tmp, st, 1);
			else //사이클 flag OFF
				dfs(tmp, st, 0);
		}
		else if (tmp != trail && !check) // 방문한 적 있는데, 바로 직전에 방문한 정점이 아님 = 사이클임!
		{
			check = 1; //사이클 flag ON
			checknorm = tmp; //이 정점을 시작으로 사이클 표시 시작

			if (!cycle[st]) //사이클에 편입 안 시켰었음
			{
				cycle[st] = ++check_cycle; //편입: check_cycle을 이 정점에 할당함
				cycle_cnt++; //사이클 정점 갯수
			}

			return;
		}
	}

	if (check && !no) //사이클 flag ON이고 사이클이 아니라고 생각했었음 -> 사이클 flag가 올라갔으니 이 정점도 사이클임
	{
		if (st == checknorm) //사이클을 시작했던 정점-> 사이클 이제 그만
			check = 0;

		if (!cycle[st]) //사이클 편입
		{
			cycle[st] = ++check_cycle;
			cycle_cnt++;
		}
	}

	return;
}

void dfs2(int st, int par_cycle) //사이클과 연결된 각 subtree에 번호를 할당하는 dfs. st: 현재 정점, par_cycle: 마지막으로 들렀던 사이클 정점
{
	int tmp;

	if (!cycle[st]) //번호 할당이 안 되어있음
		cycle[st] = par_cycle; //마지막으로 들렀던 사이클 정점과 똑같은 번호 할당

	for (int i = 0; i < (int)tree[st].size(); ++i)
	{
		tmp = tree[st][i];

		if (visit[tmp] < 2)
		{
			visit[tmp] = 2;

			if (cycle[tmp])
				dfs2(tmp, cycle[tmp]);
			else
				dfs2(tmp, par_cycle);
		}
	}

	return;
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int n, q, tmp, tmp2, tmp3, tmp4;

	cin >> n >> q;

	tree = vivi(n + 1);
	visit = cycle = vi(n + 1, 0);

	for (int i = 0; i < n; ++i)
	{
		cin >> tmp >> tmp2;

		tree[tmp].push_back(tmp2);
		tree[tmp2].push_back(tmp);
	}

	visit[1] = 1; //정점 1에서 시작
	dfs(1, 0, 0); //사이클 찾기

	for (int i = 1; i <= n; ++i) //사이클 정점 하나 찾기
	{
		if (cycle[i])
		{
			visit[i] = 2; //이 정점에서 시작
			dfs2(i, cycle[i]);  //모든 정점에 번호 할당하기

			break;
		}
	}

	for (int i = 0; i < q; ++i)
	{
		cin >> tmp >> tmp2;
 
		if (cycle_cnt % 2) //사이클 정점 갯수가 홀수?
			cout << 1; //1! 1! 1! 1!
		else
		{
			tmp3 = min(cycle[tmp], cycle[tmp2]); //a + n = b를 만들기 위함
			tmp4 = max(cycle[tmp], cycle[tmp2]); 

			if (tmp3 +(cycle_cnt / 2) == tmp4) //a + n = b?
				cout << 2;
			else
				cout << 1;
		}

		cout << '\n';
	}
	
	return 0;
}

Green55 3년 전 1

사이클의 정점 개수는 상관이 없습니다. 예제를 직접 손으로 그려보시는걸 추천드립니다. 1 과 3 사이의 경로는 1-2-3과 1-3 총 두 개입니다.

path가 2개 존재하기 위해서는 사이클을 시계방향으로 도는 것과 반시계방향으로 도는 것 둘 다 가능해야하고, 여기서 사이클의 크기가 짝수인지 홀수인지는 무관계합니다.

surung9898 3년 전 0

헉... 문제를 뭔가 착각하고 있었군요... shortest path가 몇 개인지를 세고 있었나봅니다... 감사합니다!!!!!!!

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

문제

문제

출처

ICPC

맞았습니다 나올것가태!!!! 맞았습니다 나올것가태!!!!

surung9898 3년 전 0

Green55 3년 전 1

surung9898 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말