글 읽기 - 런타임 에러 Outofbounds의 원인을 모르겠습니다.

cocoju 3년 전 0

입력값을 방정식/부등식으로 구분하여

방정식에 해당하는 노드를 Union-Find를 통해 disjointed set로 묶고

부등식에 해당하는 노드의 대표값을 단방향 그래프로 만들어

각각의 노드들에 대해 dfs를 돌려 사이클을 탐색하는 방향으로 풀고 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <string>

using namespace std;
typedef pair<int, int> pI;
int N, M;
bool ans = true;

int nodes[50005];
queue<pI> equation;
queue<pI> comparison;

//dfs용 그래프
bool visit[50005];
bool member[50005];
bool check[50005];
vector<int> graph[50005];
vector<int> graphR[50005];

int Find(int x)
{
	if (nodes[x] == x) return x;
	nodes[x] = Find(nodes[x]);
	return nodes[x];
}
bool Union(int x, int y)
{
	int X = Find(x);
	int Y = Find(y);
	if (X != Y)
	{
		nodes[Y] = X;
		return true;
	}
	return false;
}

void clear(int n)
{
	for (int i = 0; i < n; i++)
	{
		check[i] = false;
	}
}

bool dfs(int a)
{
	if (visit[a]) return true;
	if (check[a]) return false;
	check[a] = true;
	visit[a] = true;
	for (int index = 0; index < graph[a].size(); index++)
	{
		if (dfs(graph[a][index])) return true;
	}
	visit[a] = false;
	return false;
}
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		nodes[i] = i;
	}
	string buf;
	getline(cin, buf);
	//방정식과 부등식으로 분류
	for (int t = 1; t <= M; t++)
	{
		string s;
		getline(cin, s);
		int a, b; a = s[0] - '0'; b = s[4] - '0';
		if (s[2] == '=')
		{
			equation.push(make_pair(a, b));
		}
		else if (s[2] == '>')
		{
			comparison.push(make_pair(a, b));
		}
		else
		{
			comparison.push(make_pair(b, a));
		}
	}
	
	//방정식에 있는 노드 Disjointed set로 만들기
	while (!equation.empty())
	{
		int a = equation.front().first;
		int b = equation.front().second;
		equation.pop();
		Union(a, b);
	}

	//부등식에 있는 노드 단방향 그래프로 만들기
	while (!comparison.empty())
	{
		int a = Find(comparison.front().first);
		int b = Find(comparison.front().second);
		comparison.pop();
		member[a] = true;
		member[b] = true;

		if (a == b) //부등식에 있는 노드 짝이 이미 방정식에 있는 경우
		{
			ans = false;
			break;
		}
		graph[b].push_back(a);
		graphR[a].push_back(b);
	}

	//단방향 그래프에 있는 노드 각각에 dfs 돌려서 사이클 존재여부 탐색
	for (int i = 0; i < N; i++)
	{
		if (member[i] == true)
		{
			if (dfs(i))
			{
				ans = false;
				break;
			}
		}
		clear(N);//dfs가 끝나면 check배열 0으로 초기화
	}
	if (ans)
		cout << "consistent";
	else
		cout << "inconsistent";
	return 0;
}

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

문제

문제

출처

ICPC

런타임 에러 Outofbounds의 원인을 모르겠습니다.

cocoju 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말