#include <iostream> #include <vector> #include <cstdio> using namespace std; int N, M; vector< vector<int> > edges(1000001, vector<int>()); int half = 500001; int visited[1000002]; bool res_nodes[500002]; int NOT_VISITED = 0; int PATH = 1; int VISITED = 2; int dfs(int nr) { if (visited[nr] == PATH) return 1; if (visited[nr] == VISITED) return 0; visited[nr] = PATH; int sum = 0; for(std::vector<int>::iterator it = edges[nr].begin(); it != edges[nr].end(); ++it) { sum += dfs(*it); } visited[nr] = VISITED; if(sum > 0) return 1; return 0; } pair<int, int> count_cycles() { int cycles = 0; int st = 0; for(int i = 1; i <= N; i++){ visited[i] = NOT_VISITED; visited[i + half] = NOT_VISITED; } for(int i = 1; i < N; i++) { if(visited[i] == NOT_VISITED) { int d = dfs(i); if (d > 0 && st == 0) st = i; cycles += d; } } return std::make_pair(cycles, st); } int main() { scanf("%d %d", &N, &M); int begin, end; for(int i = 1; i <= M; i++){ scanf("%d %d", &begin, &end); edges[begin + half].push_back(end); } for(int i = 1; i <= N; i++)edges[i].push_back(half + i); pair<int, int> res = count_cycles(); int independent_cycles = res.first; int node = res.second; int final_nodes = 0; if (independent_cycles == 0){ printf("NIE\n"); } else if (independent_cycles > 1) { printf("0\n"); } else { for(int i = 1; i <= N; i++) { //edges[node].pop_back(); edges[i].pop_back(); res = count_cycles(); if(res.first == 0) { final_nodes++; //res_nodes[node] = true; res_nodes[i] = true; } edges[i].push_back(half+i); } printf("%d\n", final_nodes); for(int i = 1; i <= N; i++) if(res_nodes[i]) printf("%d ", i); } 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 | #include <iostream> #include <vector> #include <cstdio> using namespace std; int N, M; vector< vector<int> > edges(1000001, vector<int>()); int half = 500001; int visited[1000002]; bool res_nodes[500002]; int NOT_VISITED = 0; int PATH = 1; int VISITED = 2; int dfs(int nr) { if (visited[nr] == PATH) return 1; if (visited[nr] == VISITED) return 0; visited[nr] = PATH; int sum = 0; for(std::vector<int>::iterator it = edges[nr].begin(); it != edges[nr].end(); ++it) { sum += dfs(*it); } visited[nr] = VISITED; if(sum > 0) return 1; return 0; } pair<int, int> count_cycles() { int cycles = 0; int st = 0; for(int i = 1; i <= N; i++){ visited[i] = NOT_VISITED; visited[i + half] = NOT_VISITED; } for(int i = 1; i < N; i++) { if(visited[i] == NOT_VISITED) { int d = dfs(i); if (d > 0 && st == 0) st = i; cycles += d; } } return std::make_pair(cycles, st); } int main() { scanf("%d %d", &N, &M); int begin, end; for(int i = 1; i <= M; i++){ scanf("%d %d", &begin, &end); edges[begin + half].push_back(end); } for(int i = 1; i <= N; i++)edges[i].push_back(half + i); pair<int, int> res = count_cycles(); int independent_cycles = res.first; int node = res.second; int final_nodes = 0; if (independent_cycles == 0){ printf("NIE\n"); } else if (independent_cycles > 1) { printf("0\n"); } else { for(int i = 1; i <= N; i++) { //edges[node].pop_back(); edges[i].pop_back(); res = count_cycles(); if(res.first == 0) { final_nodes++; //res_nodes[node] = true; res_nodes[i] = true; } edges[i].push_back(half+i); } printf("%d\n", final_nodes); for(int i = 1; i <= N; i++) if(res_nodes[i]) printf("%d ", i); } return 0; } |