summaryrefslogtreecommitdiff
path: root/Year_1/Programming_2/exercises/exam_20_07_20
diff options
context:
space:
mode:
authorSanto Cariotti <santo@dcariotti.me>2021-02-06 19:56:36 +0100
committerSanto Cariotti <santo@dcariotti.me>2021-02-06 19:56:36 +0100
commitd2edbc38cac8da52f58c5cd3da6c0c625fa05736 (patch)
treea51e9a4e56fc9d4c7c9e37576dceedca3a0c72b4 /Year_1/Programming_2/exercises/exam_20_07_20
parent98f34040820dc3a964b7be59a698323e8cc6c8a3 (diff)
conf: rename
Diffstat (limited to 'Year_1/Programming_2/exercises/exam_20_07_20')
-rw-r--r--Year_1/Programming_2/exercises/exam_20_07_20/ex1.cpp39
-rw-r--r--Year_1/Programming_2/exercises/exam_20_07_20/ex2.cpp63
-rw-r--r--Year_1/Programming_2/exercises/exam_20_07_20/ex3.cpp284
-rw-r--r--Year_1/Programming_2/exercises/exam_20_07_20/ex4.cpp293
-rw-r--r--Year_1/Programming_2/exercises/exam_20_07_20/ex5.cpp285
5 files changed, 964 insertions, 0 deletions
diff --git a/Year_1/Programming_2/exercises/exam_20_07_20/ex1.cpp b/Year_1/Programming_2/exercises/exam_20_07_20/ex1.cpp
new file mode 100644
index 0000000..4f08a74
--- /dev/null
+++ b/Year_1/Programming_2/exercises/exam_20_07_20/ex1.cpp
@@ -0,0 +1,39 @@
+#include<iostream>
+#include<sstream>
+#include<fstream>
+#include<vector>
+
+using namespace std;
+int insertionsort(vector<int>& a, int n) {
+ int c = 0;
+ for(int i = 1; i < n; ++i) {
+ int j = i-1;
+ int key = a[i];
+ while(j > -1 && a[j] > key) {
+ swap(a[j+1], a[j]);
+ --j;
+ c++;
+ }
+ a[j+1] = key;
+ }
+ return c;
+}
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ int N;
+ in >> N;
+ int a, b;
+ vector<int> v;
+ for(int i = 0; i < N; ++i) {
+ in >> a >> b;
+ v.push_back(a+b);
+ }
+ out << insertionsort(v, v.size()) << endl;
+ }
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/Year_1/Programming_2/exercises/exam_20_07_20/ex2.cpp b/Year_1/Programming_2/exercises/exam_20_07_20/ex2.cpp
new file mode 100644
index 0000000..aed25e4
--- /dev/null
+++ b/Year_1/Programming_2/exercises/exam_20_07_20/ex2.cpp
@@ -0,0 +1,63 @@
+#include<iostream>
+#include<sstream>
+#include<fstream>
+#include<queue>
+
+using namespace std;
+using pi = tuple<int, int, vector<int>>;
+
+class comp {
+public:
+ bool operator()(const pi& lhs, const pi& rhs) const {
+ auto xl = get<0>(lhs);
+ auto yl = get<0>(rhs);
+
+ auto il = get<1>(lhs);
+ auto jl = get<1>(rhs);
+ if(xl == yl)
+ return il > jl;
+ return xl > yl;
+ }
+};
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ int R, C;
+ in >> R >> C;
+ vector<vector<int>> v;
+ priority_queue<pi, vector<pi>, comp> pq;
+ int k;
+ for(int i = 0; i < R; ++i) {
+ v.push_back(vector<int>{});
+ for(int j = 0; j < C; ++j) {
+ in >> k;
+ v[i].push_back(k);
+ }
+ }
+
+ int index = 0;
+ for(auto const& i : v) {
+ int s = 0;
+ pi qq;
+ for(auto const& j : i)
+ s += j;
+ get<0>(qq) = s;
+ get<1>(qq) = index++;
+ get<2>(qq) = i;
+ pq.push(qq);
+ }
+ while(!pq.empty()) {
+ auto q = pq.top();
+ pq.pop();
+ for(auto const& i : get<2>(q))
+ out << i << ' ';
+ }
+ out << endl;
+ }
+ in.close();
+ out.close();
+ return 0;
+}
diff --git a/Year_1/Programming_2/exercises/exam_20_07_20/ex3.cpp b/Year_1/Programming_2/exercises/exam_20_07_20/ex3.cpp
new file mode 100644
index 0000000..71f9c65
--- /dev/null
+++ b/Year_1/Programming_2/exercises/exam_20_07_20/ex3.cpp
@@ -0,0 +1,284 @@
+#include<iostream>
+#include<sstream>
+#include<fstream>
+
+using namespace std;
+
+template<class T>
+struct node {
+ T key;
+ node<T>* prev;
+ node<T>* right;
+ node<T>* left;
+};
+
+template<class T>
+class bst {
+public:
+ bst() : root{nullptr} , _val{0}{}
+
+ ~bst() {
+ // TODO
+ }
+
+ bst<T>* insert(initializer_list<T>&& list) {
+ for(auto const& i : list)
+ insert(i);
+
+ return this;
+ }
+
+ bst<T>* insert(T k) {
+ node<T>* nodus = new node<T>{k, nullptr, nullptr, nullptr};
+ node<T>* iter = root;
+ node<T>* prev = nullptr;
+
+ while(iter) {
+ prev = iter;
+ iter = (k < iter->key) ? iter->left : iter->right;
+ }
+
+ nodus->prev = prev;
+ if(!prev)
+ root = nodus;
+ else if(k < prev->key)
+ prev->left = nodus;
+ else
+ prev->right = nodus;
+
+ return this;
+ }
+
+ bst<T>* remove(initializer_list<T>&& list) {
+ for(auto const& i : list)
+ remove(i);
+
+ return this;
+ }
+
+ bst<T>* remove(T k) {
+ node<T>* nodus = search(k);
+ if(!nodus) return this;
+
+ if(!nodus->left) {
+ _transplant(nodus, nodus->right);
+ } else if(!nodus->right) {
+ _transplant(nodus, nodus->left);
+ } else {
+ node<T>* iter = _min(nodus->right);
+ if(iter->prev != nodus) {
+ _transplant(iter, iter->right);
+ iter->right = nodus->right;
+ iter->right->prev = iter;
+ }
+ _transplant(nodus, iter);
+ iter->left = nodus->left;
+ iter->left->prev = iter;
+ }
+
+ delete nodus;
+ return this;
+ }
+
+ node<T>* min() {
+ return _min(root);
+ }
+
+ node<T>* min(node<T>* nodus) {
+ return _min(nodus);
+ }
+
+ node<T>* max() {
+ return _max(root);
+ }
+
+ node<T>* max(node<T>* nodus) {
+ return _max(nodus);
+ }
+
+ node<T>* search(T k) {
+ node<T>* iter = root;
+ while(iter && iter->key != k)
+ iter = (iter->key > k) ? iter->left : iter->right;
+
+ return iter;
+ }
+
+ node<T>* successor(T k) {
+ node<T>* nodus = search(k);
+ if(!nodus) return nullptr;
+
+ if(nodus->right)
+ return min(nodus->right);
+
+ node<T>* prev = nodus->prev;
+ while(prev && nodus == prev->right) {
+ nodus = prev;
+ prev = prev->prev;
+ }
+
+ return prev;
+
+ }
+ node<T>* predecessor(T k) {
+ node<T>* nodus = search(k);
+ if(!nodus) return nullptr;
+
+ if(nodus->left)
+ return max(nodus->left);
+
+ node<T>* prev = nodus->prev;
+ while(prev && nodus == prev->left) {
+ nodus = prev;
+ prev = prev->prev;
+ }
+
+ return prev;
+ }
+
+ friend ostream& operator<<(ostream& os, bst<T>* tree) {
+ tree->_inorder(os, tree->root);
+ return os;
+ }
+ T sol(T k) {
+ return _max(search(k))->key;
+ }
+private:
+ int _val;
+ void _transplant(node<T>* u, node<T>* v) {
+ if(!u->prev) {
+ root = v;
+ } else if(u == u->prev->left) {
+ u->prev->left = v;
+ } else {
+ u->prev->right = v;
+ }
+
+ if(v)
+ v->prev = u->prev;
+ }
+
+ node<T>* _min(node<T>* root) {
+ node<T>* iter = root;
+ while(iter && iter->left)
+ iter = iter->left;
+
+ return iter;
+ }
+
+ node<T>* _max(node<T>* root) {
+ node<T>* iter = root;
+ while(iter && iter->right)
+ iter = iter->right;
+
+ return iter;
+ }
+
+ void _inorder(ostream& os, node<T>* root) {
+ if(root) {
+ if(root->right && root->left) {
+ _val++;
+ }
+ _inorder(os, root->left);
+ os << root->key << ' ';
+ _inorder(os, root->right);
+ }
+ }
+
+ void _preorder(ostream& os, node<T>* root) {
+ if(root) {
+ os << root->key << ' ';
+ _inorder(os, root->left);
+ _inorder(os, root->right);
+ }
+ }
+
+ void _postorder(ostream& os, node<T>* root) {
+ if(root) {
+ _inorder(os, root->left);
+ _inorder(os, root->right);
+ os << root->key << ' ';
+ }
+ }
+ node<T>* root;
+};
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ string t, comm;
+ in >> t;
+ int n;
+ switch(t.at(0)) {
+ case 'd':
+ {
+ bst<double>* b = new bst<double>{};
+ in >> n;
+ double k;
+ for(int i = 0; i < n; ++i) {
+ in >> comm;
+ stringstream tcomm(comm);
+ int ex= 0;
+ while(getline(tcomm, comm, ':')) {
+ if(ex == 0) {
+ if(comm == "ins")
+ ex = 1;
+ else
+ ex = 2;
+ } else {
+ if(ex == 1)
+ b->insert(stod(comm));
+ else
+ b->remove(stod(comm));
+ ex = 0;
+ }
+ }
+ }
+ in >> k;
+ cout << b << endl;
+ out << b->sol(k) << endl;
+
+ delete b;
+ break;
+ }
+ case 'i':
+ {
+ bst<int>* b = new bst<int>{};
+ in >> n;
+ int k;
+ for(int i = 0; i < n; ++i) {
+ in >> comm;
+ stringstream tcomm(comm);
+ int ex= 0;
+ while(getline(tcomm, comm, ':')) {
+ if(ex == 0) {
+ if(comm == "ins")
+ ex = 1;
+ else
+ ex = 2;
+ } else {
+ if(ex == 1)
+ b->insert(stoi(comm));
+ else
+ b->remove(stoi(comm));
+ ex = 0;
+ }
+ }
+ }
+ in >> k;
+ cout << b << endl;
+ out << b->sol(k) << endl;
+
+ delete b;
+ break;
+ }
+ }
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
+
diff --git a/Year_1/Programming_2/exercises/exam_20_07_20/ex4.cpp b/Year_1/Programming_2/exercises/exam_20_07_20/ex4.cpp
new file mode 100644
index 0000000..e234363
--- /dev/null
+++ b/Year_1/Programming_2/exercises/exam_20_07_20/ex4.cpp
@@ -0,0 +1,293 @@
+#include<iostream>
+#include<sstream>
+#include<fstream>
+
+using namespace std;
+
+template<class T>
+struct node {
+ T key;
+ node<T>* prev;
+ node<T>* right;
+ node<T>* left;
+};
+
+template<class T>
+class bst {
+public:
+ bst() : root{nullptr} , _val{0}{}
+
+ ~bst() {
+ // TODO
+ }
+
+ bst<T>* insert(initializer_list<T>&& list) {
+ for(auto const& i : list)
+ insert(i);
+
+ return this;
+ }
+
+ bst<T>* insert(T k) {
+ node<T>* nodus = new node<T>{k, nullptr, nullptr, nullptr};
+ node<T>* iter = root;
+ node<T>* prev = nullptr;
+
+ while(iter) {
+ prev = iter;
+ iter = (k < iter->key) ? iter->left : iter->right;
+ }
+
+ nodus->prev = prev;
+ if(!prev)
+ root = nodus;
+ else if(k < prev->key)
+ prev->left = nodus;
+ else
+ prev->right = nodus;
+
+ return this;
+ }
+
+ bst<T>* remove(initializer_list<T>&& list) {
+ for(auto const& i : list)
+ remove(i);
+
+ return this;
+ }
+
+ bst<T>* remove(T k) {
+ node<T>* nodus = search(k);
+ if(!nodus) return this;
+
+ if(!nodus->left) {
+ _transplant(nodus, nodus->right);
+ } else if(!nodus->right) {
+ _transplant(nodus, nodus->left);
+ } else {
+ node<T>* iter = _min(nodus->right);
+ if(iter->prev != nodus) {
+ _transplant(iter, iter->right);
+ iter->right = nodus->right;
+ iter->right->prev = iter;
+ }
+ _transplant(nodus, iter);
+ iter->left = nodus->left;
+ iter->left->prev = iter;
+ }
+
+ delete nodus;
+ return this;
+ }
+
+ node<T>* min() {
+ return _min(root);
+ }
+
+ node<T>* min(node<T>* nodus) {
+ return _min(nodus);
+ }
+
+ node<T>* max() {
+ return _max(root);
+ }
+
+ node<T>* max(node<T>* nodus) {
+ return _max(nodus);
+ }
+
+ node<T>* search(T k) {
+ node<T>* iter = root;
+ while(iter && iter->key != k)
+ iter = (iter->key > k) ? iter->left : iter->right;
+
+ return iter;
+ }
+
+ node<T>* successor(T k) {
+ node<T>* nodus = search(k);
+ if(!nodus) return nullptr;
+
+ if(nodus->right)
+ return min(nodus->right);
+
+ node<T>* prev = nodus->prev;
+ while(prev && nodus == prev->right) {
+ nodus = prev;
+ prev = prev->prev;
+ }
+
+ return prev;
+
+ }
+ node<T>* predecessor(T k) {
+ node<T>* nodus = search(k);
+ if(!nodus) return nullptr;
+
+ if(nodus->left)
+ return max(nodus->left);
+
+ node<T>* prev = nodus->prev;
+ while(prev && nodus == prev->left) {
+ nodus = prev;
+ prev = prev->prev;
+ }
+
+ return prev;
+ }
+
+ friend ostream& operator<<(ostream& os, bst<T>* tree) {
+ tree->_inorder(os, tree->root);
+ return os;
+ }
+ T sol(T k) {
+ auto x = search(k);
+ auto m = _max(x)->key;
+ auto mnn = _min(x);
+ T mn;
+ if(mnn->right)
+ mn = _min(mnn->right)->key;
+ else
+ mn = mnn->key;
+ cout << m << ' ' << mn << endl;
+ return m - mn;
+ }
+private:
+ int _val;
+ void _transplant(node<T>* u, node<T>* v) {
+ if(!u->prev) {
+ root = v;
+ } else if(u == u->prev->left) {
+ u->prev->left = v;
+ } else {
+ u->prev->right = v;
+ }
+
+ if(v)
+ v->prev = u->prev;
+ }
+
+ node<T>* _min(node<T>* root) {
+ node<T>* iter = root;
+ while(iter && iter->left)
+ iter = iter->left;
+
+ return iter;
+ }
+
+ node<T>* _max(node<T>* root) {
+ node<T>* iter = root;
+ while(iter && iter->right)
+ iter = iter->right;
+
+ return iter;
+ }
+
+ void _inorder(ostream& os, node<T>* root) {
+ if(root) {
+ if(root->right && root->left) {
+ _val++;
+ }
+ _inorder(os, root->left);
+ os << root->key << ' ';
+ _inorder(os, root->right);
+ }
+ }
+
+ void _preorder(ostream& os, node<T>* root) {
+ if(root) {
+ os << root->key << ' ';
+ _inorder(os, root->left);
+ _inorder(os, root->right);
+ }
+ }
+
+ void _postorder(ostream& os, node<T>* root) {
+ if(root) {
+ _inorder(os, root->left);
+ _inorder(os, root->right);
+ os << root->key << ' ';
+ }
+ }
+ node<T>* root;
+};
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ string t, comm;
+ in >> t;
+ int n;
+ switch(t.at(0)) {
+ case 'd':
+ {
+ bst<double>* b = new bst<double>{};
+ in >> n;
+ double k;
+ for(int i = 0; i < n; ++i) {
+ in >> comm;
+ stringstream tcomm(comm);
+ int ex= 0;
+ while(getline(tcomm, comm, ':')) {
+ if(ex == 0) {
+ if(comm == "ins")
+ ex = 1;
+ else
+ ex = 2;
+ } else {
+ if(ex == 1)
+ b->insert(stod(comm));
+ else
+ b->remove(stod(comm));
+ ex = 0;
+ }
+ }
+ }
+ in >> k;
+ cout << b << endl;
+ out << b->sol(k) << endl;
+
+ delete b;
+ break;
+ }
+ case 'i':
+ {
+ bst<int>* b = new bst<int>{};
+ in >> n;
+ int k;
+ for(int i = 0; i < n; ++i) {
+ in >> comm;
+ stringstream tcomm(comm);
+ int ex= 0;
+ while(getline(tcomm, comm, ':')) {
+ if(ex == 0) {
+ if(comm == "ins")
+ ex = 1;
+ else
+ ex = 2;
+ } else {
+ if(ex == 1)
+ b->insert(stoi(comm));
+ else
+ b->remove(stoi(comm));
+ ex = 0;
+ }
+ }
+ }
+ in >> k;
+ cout << b << endl;
+ out << b->sol(k) << endl;
+
+ delete b;
+ break;
+ }
+ }
+ }
+
+ in.close();
+ out.close();
+ return 0;
+}
+
diff --git a/Year_1/Programming_2/exercises/exam_20_07_20/ex5.cpp b/Year_1/Programming_2/exercises/exam_20_07_20/ex5.cpp
new file mode 100644
index 0000000..dd8fc98
--- /dev/null
+++ b/Year_1/Programming_2/exercises/exam_20_07_20/ex5.cpp
@@ -0,0 +1,285 @@
+#include<iostream>
+#include<vector>
+#include<algorithm>
+#include<queue>
+#include<stack>
+#include<fstream>
+#define INF 99999999
+#define W -1
+#define G 0
+#define B 1
+
+using namespace std;
+
+template<class H>
+class graph {
+public:
+ graph(int len) : _len{len}, _nodes{0}, _edges{0} {
+ _k = new H*[len];
+ _adj = new vector<int>[len];
+ _colors = new int[len];
+ _d = new int[len];
+ _f = new int[len];
+ _p = new int[len];
+
+ for(int i = 0; i < len; ++i) {
+ _k[i] = nullptr;
+ }
+ }
+ ~graph() {
+ delete[] _k;
+ delete[] _adj;
+ }
+
+ graph<H>* add_node(H x) {
+ if(_index(x) > -1) return this;
+ if(_nodes == _len) return this;
+ _k[_nodes++] = new H(x);
+
+ return this;
+ }
+ graph<H>* add_edge(H u, H v) {
+ int i = _index(u);
+ int j = _index(v);
+ if(i < 0 || j < 0) return this;
+
+ if(find(_adj[i].begin(), _adj[i].end(), j) == _adj[i].end()) {
+ _adj[i].push_back(j);
+ }
+ return this;
+ }
+ void print() {
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "(" << *_k[i] << ", " << i << "): ";
+ for(auto const& j : _adj[i]) {
+ cout << "(" << *_k[j] << ", " << j << ") ";
+ }
+ cout << endl;
+ }
+ }
+ void dfsvisit(int u, bool visited[]) {
+ visited[u] = true;
+ cout << "(" << *_k[u] << ", " << u << ") ";
+ for(auto const& i : _adj[u]) {
+ if(!visited[i])
+ dfsvisit(i, visited);
+ }
+ }
+ int dfsvisit(int u) {
+ int cycle = 0;
+ _colors[u] = G;
+ _d[u] = _time++;
+
+ for(auto const& j : _adj[u]) {
+ if(_colors[j] == W)
+ cycle |= dfsvisit(j);
+ }
+
+ _colors[u] = B;
+ _stack.push(u);
+ _f[u] = _time++;
+ return cycle;
+ }
+ int dfs() {
+ int cycle = 0;
+ for(int i = 0; i < _nodes; ++i) {
+ _colors[i] = W;
+ }
+ _time = 0;
+ for(int i = 0; i < _nodes; ++i) {
+ if(_colors[i] == W)
+ cycle |= dfsvisit(i);
+ else if(_colors[i] == G)
+ cycle = 1;
+ }
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "(" << *_k[i] << ", " << i << "): [" << _d[i] << "," << _f[i] << "]" << endl;
+ }
+ return cycle;
+ }
+
+ void top_sort() {
+ int cycle = dfs();
+ if(cycle) {
+ cout << "cyclic graph!" << endl;
+ return;
+ }
+ int* s = new int[_nodes];
+ for(int i = 0; i < _nodes; ++i) s[i] = i;
+ _sort(s, _nodes, _f);
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "(" << s[i] << ", " << _f[s[i]] << ") ";
+ }
+
+ }
+
+ void bfs(H v) {
+ int s = _index(v);
+ if(s < 0) return;
+
+ for(int i = 0; i < _nodes; ++i) {
+ _colors[i] = W;
+ _d[i] = INF;
+ _p[i] = -1;
+ }
+ _colors[s] = G;
+ _d[s] = 0;
+ queue<int> q;
+ q.push(s);
+ while(!q.empty()) {
+ int u = q.front();
+ q.pop();
+ for(auto const& j : _adj[u]) {
+ if(_colors[j] == W) {
+ _colors[j] = G;
+ _d[j] = _d[u]+1;
+ _p[j] = u;
+ q.push(j);
+ }
+ }
+ _colors[u] = B;
+ }
+ for(int i = 0; i < _nodes; ++i) {
+ cout << "(" << *_k[i] << ", " << i << "): [" << _d[i] << "]" << endl;
+ }
+ }
+ int ssc() {
+ dfs();
+ cout << endl << endl;
+ bool* visited = new bool[_nodes];
+ for(int i = 0; i < _nodes; ++i)
+ visited[i] = false;
+ int count = 0;
+ while(!_stack.empty()) {
+ int v = _stack.top();
+ _stack.pop();
+ if(!visited[v]) {
+ dfsvisit(v, visited);
+ count++;
+ cout << endl;
+ }
+ }
+ delete[] visited;
+ return count;
+ }
+private:
+ graph<H>* _transpose() {
+ graph<H>* g = new graph<H>{_len};
+ for(int i = 0; i < _nodes; ++i) {
+ g->add_node(*_k[i]);
+ }
+
+ for(int i = 0; i < _nodes; ++i) {
+ for(auto const& j : _adj[i]) {
+ g->add_edge(j, i);
+ }
+ }
+
+ return g;
+ }
+ void _sort(int* d, int n, int* s) {
+ for(int i = -1; i < n; ++i) {
+ int j = i-1;
+ while(j > -1 && s[d[j+1]]>s[d[j]]) {
+ swap(d[s[j+1]], d[s[j]]);
+ --j;
+ }
+ }
+ }
+ int _index(H x) {
+ for(int i = 0; i < _nodes; ++i)
+ if(*_k[i] == x) return i;
+
+ return -1;
+ }
+ stack<int> _stack;
+ H** _k;
+ vector<int>* _adj;
+ int _len, _nodes, _edges;
+ int* _colors;
+ int _time;
+ int* _d;
+ int* _f;
+ int* _p;
+};
+
+int main() {
+ ifstream in("input.txt");
+ ofstream out("output.txt");
+
+ for(int ts = 0; ts < 100; ++ts) {
+ int n, e;
+ in >> n>>e;
+ string t;
+ in >> t;
+ char _t;
+ switch(t.at(0)){
+ case 'd':{
+ graph<double>* g = new graph<double>{n};
+ double x, y;
+ for(int i = 0; i < n; ++i) {
+ in >> x;
+ g->add_node(x);
+ }
+ for(int i = 0; i < e; ++i) {
+ in >>_t;
+ in >> x >> y;
+ in >> _t;
+ g->add_edge(x, y);
+ g->add_edge(y, x);
+ }
+ g->print();
+ cout << endl << endl;
+ out << g->ssc()<<endl;
+ delete g;
+ break;
+ }
+ case 'i':{
+
+ graph<int>* g = new graph<int>{n};
+ int x, y;
+ for(int i = 0; i < n; ++i) {
+ in >> x;
+ g->add_node(x);
+ }
+ for(int i = 0; i < e; ++i) {
+ in >>_t;
+ in >> x >> y;
+ in >> _t;
+ g->add_edge(x, y);
+ g->add_edge(y, x);
+ }
+ g->print();
+ cout << endl << endl;
+ out << g->ssc()<<endl;
+ delete g;
+ break;
+ }
+ case 'c': {
+
+ graph<char>* g = new graph<char>{n};
+ char x, y;
+ for(int i = 0; i < n; ++i) {
+ in >> x;
+ g->add_node(x);
+ }
+ for(int i = 0; i < e; ++i) {
+ in >>_t;
+ in >> x >> y;
+ in >> _t;
+ g->add_edge(x, y);
+ g->add_edge(y, x);
+ }
+ g->print();
+ cout << endl << endl;
+ out << g->ssc()<<endl;
+ delete g;
+ break;
+ }
+ }
+ }
+ in.close();
+ out.close();
+ return 0;
+}
+