/* Solution for Season 6 Round 6 Problem 3 Senior Author: Anton Chernev */ #include #include #include #include using std::vector; using std::min; using std::stack; const int MAX_N = 100001; int N, M; vector edges[MAX_N]; stack processed; int label[MAX_N], minReachable[MAX_N], nextLabel; bool isProcessed[MAX_N], suitable[MAX_N]; void read() { int x, y; scanf("%d%d", &N, &M); for(size_t i = 0; i < M; ++i) { scanf("%d%d", &x, &y); edges[x].push_back(y); if(x == y) suitable[x] = true; } } int dfs(int vertex) { label[vertex] = minReachable[vertex] = nextLabel++; processed.push(vertex); isProcessed[vertex] = true; for(size_t i = 0; i < edges[vertex].size(); i++) if(label[edges[vertex][i]]) { if(isProcessed[edges[vertex][i]]) minReachable[vertex] = min(minReachable[vertex], minReachable[edges[vertex][i]]); } else minReachable[vertex] = min(minReachable[vertex], dfs(edges[vertex][i])); if(minReachable[vertex] == label[vertex]) { if(processed.top() != vertex) suitable[vertex] = true; while(processed.top() != vertex) { isProcessed[processed.top()] = false; processed.pop(); } isProcessed[vertex] = false; processed.pop(); } else suitable[vertex] = true; return minReachable[vertex]; } void print() { for(size_t i = 1; i <= N; ++i) if(suitable[i]) printf("%d\n", i); } int main() { freopen("tourism.in", "r", stdin); freopen("tourism.out", "w", stdout); read(); nextLabel = 1; for(size_t i = 1; i <= N; ++i) if(!label[i]) dfs(i); print(); } /* */