std::basic_stringstream

std::basic_stringstream

• The class template std::basic_stringstream implements input and output operations on string based streams. It effectively stores an instance of std::basic_string and performs the input and output operations on it.

• In C++, stringstream is useful when retrieving suitable information for the required data type from a given string. Extracts information of data types that match a string except for spaces and ‘\n’ from stringstream.

• Example

#include <iostream>
#include <iomanip>
#include <sstream>
 
int main()
{
    std::string input = "41 3.14 false hello world";
    std::istringstream stream(input);
    int n;
    double f;
    bool b;
 
    stream >> n >> f >> std::boolalpha >> b;
    std::cout << "n = " << n << '\n'
              << "f = " << f << '\n'
              << "b = " << std::boolalpha << b << '\n';
 
    // extract the rest using the streambuf overload
    stream >> std::cout.rdbuf();
    std::cout << '\n';
}

• Output n = 41
  f = 3.14
  b = false
  hello world

MST Minimun Spanning Tree

Kruskal

• Kruskal’s Algorithm
  • Creating the least cost tree from the graph

  • Kruskal’s algorithm is used to connect all vertices in the graph with the lowest cost, and finds a situation where the sum of weights is the minimum when a connecting line with no cycles is drawn including all vertices in the graph. Use Kruskal’s Algorithm

  • SOLUTION : UnionFind
    • Point : First, based on the weight of the edges, sort the vertices in ascending order, and include vertices only if the vertices satisfy each other’s subset.

      Prim

• Prim Algorithm : method of adding vertices
  • To construct the MST minimum cost spanning tree, we do not select an edge, but select a random vertex.
  • From there, continue to add vertices one by one while watching the connection relationship of the graph.

  • Expand the tree while adding vertices When number of vertices are completed as N, the tree is completed.

  • SOLUTION : priority_queue - UseMinimum heap
• prim & kruskal difference
  • Prim’s algorithm selects a vertex and selects the lowest cost vertex associated with it
  • Kruskal’s algorithm lists all costs sequentially and selects the lowest cost edges (kidneys)

UnionFind

UnionFind : A disjoint-set data strsubsetsucture is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) . A union-find algorithm is an algorithm that performs two useful operations on such a data structure

• Union Find Algorithm : Algorithm used to express Disjoint Set
  • Disjoint Set
  • implemented by tree
• Example

#include<bits/stdc++.h>
using namespace std;

int unf[1002]; // tree
int node1, node2;

int Find(int v) { //Find Parent Node
	if(unf[v] == v) return v;
	else return unf[v] = Find(unf[v]); //minimize path - memoization  
}

void Union(int a, int b) {
	node1 = Find(a);
	node2 = Find(b);
	
	if(node1 != node2) unf[node1] = node2; //organize tree structure
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, x, y;
	freopen("input.txt", "rt", stdin);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		unf[i] = i; // initialize tree
	}
	
	for(int i = 1; i <= m; i++) {
		cin >> x >> y;
		Union(x, y);
	}
	
	cin >> x >> y;
	node1 = Find(x);
	node2 = Find(y);
	if(node1 != node2) cout << "Not in the same set"<< "\n"; // if parentNode not same, not in same set
	else cout << "In the same set"<< "\n"; // same parent node, same set
	
	for(int i = 1; i <= 5; i++) cout << unf[i] << " ";
	
 	return 0;
}