#include using namespace std; /* [Challenge] Galaxies Far Far Away You work for a space-communications company and you are told that a space network should be free of any loops. Otherwise loops will cause reverberation of the signal. You are given matrices that represent different networks of some spaceships in galaxies far far away. The matrices represent how the spaceships connect to each other(0 not connected, 1 is connected). The matrices are "adjacency matrices". The question is are there any loops in those networks? If there are loops, how many connections should be removed? Note: a "tree graph" is a graph with no loops. https://code.sololearn.com/ c0BR61aFYpJn/?ref=app */ //change input here const int N = 8; vector> net { { 0, 1, 1, 0, 0, 0, 0, 0 }, { 1, 0, 0, 0, 0, 1, 0, 0 }, { 1, 0, 0, 1, 1, 0, 0, 0 }, { 0, 0, 1, 0, 0, 0, 0, 1 }, { 0, 0, 1, 0, 0, 0, 1, 1 }, { 0, 1, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 1, 0, 0, 1 }, { 0, 0, 0, 1, 1, 0, 1, 0 } }; vector adj[N]; vector vis (N); vector par (N); vector cy; vector> ans; bool loop; int cnt; // p = parent, t = target void dfs(int p, int t) { if (vis[t] == 2) return; if (vis[t] == 1) { loop = true; cnt++; cy.push_back(t); cy.push_back(p); int k = p; while (k != t) { k = par[k]; cy.push_back(k); } ans.push_back(cy); cy.clear(); return; } par[t] = p; vis[t] = 1; for (auto i : adj[t]) { if (i != p) dfs(t, i); } vis[t] = 2; return; } void print(vector> v) { for (auto i : v) { for (auto c : i) { cout << c << " "; } cout << "\n"; } } int main() { // create adjacency list for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (net[i][j] == 1) { adj[i].push_back(j); } } } // dfs for (int i = 0; i < N; i++) { if (vis[i] != 2) dfs(i, i); } cout << (loop ? "Cycle\n":"No cycle\n"); // print cycles print(ans); cout << "Number of connections to " << "remove: " << cnt << "\n"; return 0; }