#include <stdio.h> #include <set> #include <vector> using namespace std; struct Node { vector<int> next; bool visited; int number; }; int dfs(Node *graph, int start, int number, int removeNode = -1) { Node *node = graph + start; node->visited = true; for(vector<int>::iterator it = node->next.begin(); it != node->next.end(); ++it) { if(*it == removeNode) { continue; } if(!graph[*it].visited) { number = dfs(graph, *it, number, removeNode); } } node->number = number--; return number; } void clearVisited(Node *graph, int size) { for(int i = 0; i < size; ++i) { graph[i].visited = false; } } bool isAcyclic(Node *graph, int size, int removeNode = -1) { clearVisited(graph, size); int number = size; for(int i = 0; i < size; ++i) { if(!graph[i].visited) { number = dfs(graph, i, number, removeNode); } } for(int i = 0; i < size; ++i) { if(i == removeNode) { continue; } Node *node = graph + i; for(vector<int>::iterator it = node->next.begin(); it != node->next.end(); ++it) { if(*it == removeNode) { continue; } if(node->number > graph[*it].number) { return false; } } } return true; } int main() { int n, m; scanf("%d %d", &n, &m); Node *graph = new Node[n]; for(int i = 0; i < m; ++i) { int a, b; scanf("%d %d", &a, &b); graph[a - 1].next.push_back(b - 1); } if(isAcyclic(graph, n)) { printf("NIE\n"); } else { vector<int> result; for(int i = 0; i < n; ++i) { if(isAcyclic(graph, n, i)) { result.push_back(i); } } printf("%d\n", result.size()); for(vector<int>::iterator it = result.begin(); it != result.end(); ++it) { printf("%d ", *it + 1); } printf("\n"); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include <stdio.h> #include <set> #include <vector> using namespace std; struct Node { vector<int> next; bool visited; int number; }; int dfs(Node *graph, int start, int number, int removeNode = -1) { Node *node = graph + start; node->visited = true; for(vector<int>::iterator it = node->next.begin(); it != node->next.end(); ++it) { if(*it == removeNode) { continue; } if(!graph[*it].visited) { number = dfs(graph, *it, number, removeNode); } } node->number = number--; return number; } void clearVisited(Node *graph, int size) { for(int i = 0; i < size; ++i) { graph[i].visited = false; } } bool isAcyclic(Node *graph, int size, int removeNode = -1) { clearVisited(graph, size); int number = size; for(int i = 0; i < size; ++i) { if(!graph[i].visited) { number = dfs(graph, i, number, removeNode); } } for(int i = 0; i < size; ++i) { if(i == removeNode) { continue; } Node *node = graph + i; for(vector<int>::iterator it = node->next.begin(); it != node->next.end(); ++it) { if(*it == removeNode) { continue; } if(node->number > graph[*it].number) { return false; } } } return true; } int main() { int n, m; scanf("%d %d", &n, &m); Node *graph = new Node[n]; for(int i = 0; i < m; ++i) { int a, b; scanf("%d %d", &a, &b); graph[a - 1].next.push_back(b - 1); } if(isAcyclic(graph, n)) { printf("NIE\n"); } else { vector<int> result; for(int i = 0; i < n; ++i) { if(isAcyclic(graph, n, i)) { result.push_back(i); } } printf("%d\n", result.size()); for(vector<int>::iterator it = result.begin(); it != result.end(); ++it) { printf("%d ", *it + 1); } printf("\n"); } return 0; } |