이것이 코딩테스트다 - 10) 그래프

 

 

 

 

8,9,10 단원은 백준, 프로그래머스 달린다고 생각하고 복습 제대로 해야한다. 

 

 

엉망진창 와진창이다. 

 

 

10.1) 팀 결성

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 1e9


using namespace std;

int n, m;
int parent[100000];

int find_parent(int parent[100000], int x) {
	if (parent[x] != x) {
		parent[x] = find_parent(parent, parent[x]);
	}
	return parent[x];
}

void union_parent(int parent[100000], int a, int b) {
	a = find_parent(parent, a);
	b = find_parent(parent, b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}
int main() {

	cin >> n >> m;

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

		int num, a, b;
		cin >> num >> a >> b;
		if (num == 0) {
			union_parent(parent, a, b);
		}
		else if (num == 1) {
			if (find_parent(parent, a) == find_parent(parent, b)) cout << "YES" << endl;
			else cout << "NO" << endl;
		}
	}

	return 0;


}

 

 

 

 

10.2) 도시 분할 계획

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 1e9


using namespace std;

int n, m, result = 0;
int parent[100001];
vector<pair<int, pair<int, int>>> edges;

int find_parent(int parent[100001], int x) {
	if (parent[x] != x)
		parent[x] = find_parent(parent, parent[x]);
	return parent[x];
}
void union_parent(int parent[100001], int a, int b) {
	a = find_parent(parent, a);
	b = find_parent(parent, b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}
int main() {

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		parent[i] = i;
	}
	for (int i = 0; i < m; i++) {
		int a, b, cost;
		cin >> a >> b >> cost;
		edges.push_back({ cost,{a,b} });
	}

	sort(edges.begin(), edges.end());

	int last = 0;

	for (int i = 0; i < edges.size(); i++)
	{
		int cost = edges[i].first;
		int a = edges[i].second.first;
		int b = edges[i].second.second;

		if (find_parent(parent, a) != find_parent(parent, b))
		{
			union_parent(parent, a, b);
			result += cost;
			last = cost;
		}

	}

	cout << result - last << endl;

	return 0;
}

 

 

 

 

10.3) 커리큘럼

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF 1e9


using namespace std;

int n;
int indegree[501];
vector<int> graph;
int times[501];


//´Ù½ÃÇ®±â

int main() {
	vector<int> result(501);

	cin >> n;

	queue<int> q;

	for (int i = 0; i < n; i++)
	{
		if (indegree[i] == 0)
			q.push(i);
	}

	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		for (int i = 0; i < graph[now].size(); i++) {

		}
	}

	return 0;
}