글 읽기 - 1197 번 최소 스패닝 트리

qudduq06 2년 전 0

크루스칼 개념을 알고서 순서대로 코드를 구현해보았는데 틀렸다고 나옵니다 어느 부분이 틀렸는지 궁금합니다

#include<iostream>
#include<vector>
#include<map>
#include<queue>

using namespace std;
#define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0); setvbuf(stdout, nullptr, _IOFBF, BUFSIZ);
int V, E;

struct Edge
{
	int Node_1 = 0;
	int Node_2 = 0;
	int weight = 0;

	bool operator < (const Edge &var) const
	{
		if (var.weight < weight)
			return true;

		return false;
	}
};

struct Node
{
	bool visit = false;
	int group = 0;
	vector<int> node;
};


priority_queue<Edge> Edges;
vector<Node> Nodes;
vector<int> Groups;
int answer = 0;

void dfs(int node,int group)
{
	if (Nodes[node].group == group)
		return;

	Nodes[node].group = group;
	for (int i = 0; i < Nodes[node].node.size(); i++)
	{
		dfs(Nodes[node].node[i], group);
	}
}

void SetNode(int node,int link,int group)
{
	Nodes[node].visit = true;
	Nodes[node].group = group;
	Nodes[node].node.push_back(link);
}

void Solution()
{
	int size = Edges.size();
	int count = 0;
	int group = 1;
	for (int i = 0; i < size; i++)
	{
		Edge tmp = Edges.top();
		Edges.pop();

		if (Nodes[tmp.Node_1].visit == false && Nodes[tmp.Node_2].visit == false)
		{
			SetNode(tmp.Node_1, tmp.Node_2, group);
			SetNode(tmp.Node_2, tmp.Node_1, group);

			answer += tmp.weight;
			group++;
		}
		else if (Nodes[tmp.Node_1].visit == false)
		{
			SetNode(tmp.Node_1, tmp.Node_2, Nodes[tmp.Node_2].group);
			Nodes[tmp.Node_2].node.push_back(tmp.Node_1);

			answer += tmp.weight;
		}
		else if (Nodes[tmp.Node_2].visit == false)
		{
			SetNode(tmp.Node_2, tmp.Node_1, Nodes[tmp.Node_1].group);
			Nodes[tmp.Node_1].node.push_back(tmp.Node_2);

			answer += tmp.weight;
		}
		else if(Nodes[tmp.Node_1].visit && Nodes[tmp.Node_2].visit)
		{
			if (Nodes[tmp.Node_1].group != Nodes[tmp.Node_2].group)
			{
				dfs(tmp.Node_2, Nodes[tmp.Node_1].group);
				Nodes[tmp.Node_2].node.push_back(tmp.Node_1);
				answer += tmp.weight;
			}
		}
		
	}
}


int main()
{
	fastio;

	cin >> V >> E;

	Nodes.resize(100001);

	int node1, node2, weight;
	for (int i = 0; i < E; i++)
	{
		cin >> node1 >> node2 >> weight;
		Edge tmp = { node1,node2,weight };
		Edges.push(tmp);
	}

	Solution();
	cout << answer;
	


	return 0;
}

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

문제

문제

출처

ICPC

1197 번 최소 스패닝 트리

qudduq06 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말