Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- class Task {
- vector<int> size;
- vector<int> set_parent_2007;
- vector<vector<int>> kitties;
- public:
- Task();
- Task(int n) {
- set_parent_2007 = vector<int>(n);
- size = vector<int>(n, 1);
- kitties = vector<vector<int>>(n);
- for (int i = 0; i < n; i++) {
- set_parent_2007[i] = i;
- kitties[i].emplace_back(i + 1);
- }
- }
- int get_set(int v) {
- if (set_parent_2007[v] == v)
- return v;
- return set_parent_2007[v] = get_set(set_parent_2007[v]);
- }
- void my_swap(int &a, int &b){
- int tmp = a;
- a = b;
- b = tmp;
- }
- void join_sets(int set1, int set2) {
- set1 = get_set(set1);
- set2 = get_set(set2);
- if (set1 != set2) {
- if (size[set1] < size[set2]) {
- my_swap(set1, set2);
- }
- set_parent_2007[set2] = set1;
- size[set1] += size[set2];
- kitties[set1].insert(kitties[set1].end(), kitties[set2].begin(), kitties[set2].end());
- kitties[set2].clear();
- }
- }
- vector<int> get_content(){
- return kitties[get_set(0)];
- }
- };
- int main() {
- int n;
- cin >> n;
- Task task(n);
- for (int i = 0; i < n - 1; i++){
- int v1, v2;
- cin >> v1 >> v2;
- task.join_sets(v1 - 1, v2 - 1);
- }
- vector<int> answer = task.get_content();
- for (int i = 0; i < answer.size(); i++)
- cout << answer[i] << ' ';
- return 0;
- }
- //
- // 4
- //
- #include <iostream>
- #include <vector>
- using namespace std;
- class Task {
- vector<int> size;
- vector<int> set_parent_2007;
- vector<vector<int>> kitties;
- int k = 0;
- public:
- Task();
- Task(int n) {
- k = n;
- set_parent_2007 = vector<int>(n);
- size = vector<int>(n, 1);
- kitties = vector<vector<int>>(n);
- for (int i = 0; i < n; i++) {
- set_parent_2007[i] = i;
- kitties[i].emplace_back(i + 1);
- }
- }
- int get_set(int v) {
- if (set_parent_2007[v] == v)
- return v;
- return set_parent_2007[v] = get_set(set_parent_2007[v]);
- }
- void my_swap(int &a, int &b){
- int tmp = a;
- a = b;
- b = tmp;
- }
- void join_sets(int set1, int set2) {
- set1 = get_set(set1);
- set2 = get_set(set2);
- if (set1 != set2) {
- if (size[set1] < size[set2]) {
- my_swap(set1, set2);
- }
- set_parent_2007[set2] = set1;
- size[set1] += size[set2];
- kitties[set1].insert(kitties[set1].end(), kitties[set2].begin(), kitties[set2].end());
- kitties[set2].clear();
- k--;
- }
- }
- int get_content(){
- return k;
- }
- };
- int main() {
- int n;
- cin >> n;
- Task a(n);
- for (int i = 0; i < n; i++){
- int v;
- cin >> v;
- a.join_sets(i, v - 1);
- }
- cout << a.get_content();
- return 0;
- }
- //
- // 3
- //
- #include <iostream>
- #include <vector>
- using namespace std;
- vector<int> color;
- vector<vector<int>> polkovnik;
- vector<int> rota;
- void dfs(int v, int parent){
- color[v] = 1;
- for (auto &i : polkovnik[v]){
- if (color[i] == 0){
- dfs(i, v);
- }
- if (color[i] == 1){
- cout << "No";
- exit(0);
- }
- }
- rota.push_back(v + 1);
- color[v] = 2;
- }
- int main() {
- int n, m;
- cin >> n >> m;
- color = vector<int>(n);
- polkovnik = vector<vector<int>>(n);
- for (int i = 0; i < m; i++){
- int nije, vyshe;
- cin >> nije >> vyshe;
- polkovnik[nije - 1].emplace_back(vyshe - 1);
- }
- for (int i = 0; i < n; i++){
- if (!color[i]){
- dfs(i, -1);
- }
- }
- cout << "Yes" << endl;
- for (int i = 0; i < n; i++){
- cout << rota[n - 1 - i] << ' ';
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment