Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- #include <queue>
- struct Node {
- std::vector<int> neighbors;
- };
- class ListGraph {
- private:
- std::vector<Node> nodes;
- std::vector<bool> visited;
- int size;
- public:
- ListGraph(int sz) {
- /* Nodes are numbered 1 to N, not 0 to N. */
- size = sz;
- nodes.resize(sz + 1);
- for (int i = 0; i < sz + 1; i++)
- visited.push_back(false);
- }
- ~ListGraph() {}
- void addEdge(int src, int dst) {
- nodes[src].neighbors.push_back(dst);
- }
- /* you might want to write your own compare function.. check the problem statement */
- static bool compare_groups(std::vector<int> v1, std::vector<int> v2) {
- /* TODO: compare 2 groups properly */
- return v1[0] < v2[0];
- }
- /* get all groups in the classroom */
- void dfs(int nod, std::vector<bool> &viz, std::vector<int> &bis) {
- bis.push_back(nod);
- viz[nod] = 1;
- for (int i = 0; i < nodes[nod].neighbors.size(); i++) {
- if (viz[nodes[nod].neighbors[i]] == 0) {
- dfs(nodes[nod].neighbors[i], viz, bis);
- }
- }
- }
- std::vector<std::vector<int> > get_groups() {
- std::vector<std::vector<int> > bisericute;
- /* TODO: do your magic */
- int nr = 0;
- for (int i = 1; i <= size; i++) {
- if (visited[i] == false) {
- bisericute.push_back({});
- dfs(i, visited, bisericute[nr]);
- std::sort(bisericute[nr].begin(), bisericute[nr].end());
- nr++;
- }
- }
- /* TODO: return 'bisericute' sorted as described in the problem statement */
- std::sort(bisericute.begin(), bisericute.end(), compare_groups);
- return bisericute;
- }
- };
- int main() {
- /* DO NOT CHANGE ANYTHING HERE! */
- int N, M, from, to;
- std::vector<std::vector<int> > bisericute;
- std::cin >> N >> M;
- ListGraph g(N);
- for (int i = 0; i < M; i++) {
- std::cin >> from >> to;
- g.addEdge(from, to);
- g.addEdge(to, from);
- }
- bisericute = g.get_groups();
- std::cout << bisericute.size() << std::endl;
- for (int i = 0; i < bisericute.size(); i++) {
- for (int j = 0; j < bisericute[i].size(); j++) {
- std::cout << bisericute[i][j] << " ";
- }
- std::cout << std::endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement