Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- #define NMAX 103
- #define PARTIAL 1
- #define COMPLETED 2
- bool adjm[NMAX][NMAX];
- int cycles[NMAX][NMAX], cycleNr;
- int n, m, color[NMAX], daddy[NMAX], pre[NMAX];
- void read() {
- cin >> n >> m;
- for (int a, b, i = 0; i < m; i++) {
- cin >> a >> b;
- adjm[a][b] = adjm[b][a] = true;
- }
- }
- void dfs(int node, int last) {
- if (color[node] == COMPLETED) {
- return;
- }
- if (color[node] == PARTIAL) {
- cycleNr++;
- int currNode = last;
- cycles[cycleNr][++cycles[cycleNr][0]] = currNode;
- while (currNode != node) {
- currNode = pre[currNode];
- cycles[cycleNr][++cycles[cycleNr][0]] = currNode;
- }
- cout << endl;
- return;
- }
- pre[node] = last;
- color[node] = PARTIAL;
- for (int to = 1; to <= n; to++) {
- if (adjm[node][to] && to != last) {
- dfs(to, node);
- }
- }
- color[node] = COMPLETED;
- }
- void display() {
- if (!cycleNr) {
- puts("Acyclic!");
- }
- for (int i = 1; i <= cycleNr; i++) {
- cout << "cycle num. " << i << ": ";
- bool fr[NMAX] = {}, elementary = true;
- for (int j = 1; j <= *cycles[i]; j++) {
- cout << cycles[i][j] << ' ';
- elementary = elementary && !fr[cycles[i][j]];
- fr[cycles[i][j]] = true;
- }
- if (elementary)
- puts("-elementary");
- else
- puts("-neelementary");
- }
- }
- int main() {
- read();
- for (int i = 1; i <= n; i++)
- dfs(i, -1);
- display();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement