Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stack>
- #include <vector>
- using namespace std;
- struct Graph {
- int N;
- vector<int> order;
- vector<vector<int>> g;
- vector<vector<int>> g_reversed;
- vector<pair<int,int>> s;
- Graph(int V) {
- N = V;
- g = vector<vector<int>>(V);
- g_reversed = vector<vector<int>>(V);
- }
- void DFS(int v, vector<bool> &used, stack<int> &s) {
- used[v] = true;
- for (auto i: g[v]) {
- if (!used[i]) {
- DFS(i, used, s);
- }
- }
- s.push(v);
- }
- void DFS_REVERSED(int v, vector<bool> &used) {
- used[v] = true;
- order.push_back(v);
- for (auto i: g_reversed[v]) {
- if (!used[i]) {
- DFS_REVERSED(i, used);
- }
- }
- }
- void addEdge(int from, int to) {
- g[from].push_back(to);
- g_reversed[to].push_back(from);
- s.push_back(make_pair(from, to));
- }
- void solve() {
- vector<bool> used(N);
- stack<int> Stack;
- for (int i = 0; i < N; i++) {
- if (!used[i]) {
- DFS(i, used, Stack);
- }
- }
- used.assign(N, false);
- vector<int> component_for_v(N);
- int count = 0;
- while (!Stack.empty()) {
- int a = Stack.top();
- Stack.pop();
- if (!used[a]) {
- DFS_REVERSED(a, used);
- for (auto &i: order) {
- component_for_v[i] = count + 1;
- }
- count++;
- order.clear();
- }
- }
- /*cout << count << endl;
- for (auto &i: component_for_v) {
- cout << i << " ";
- }*/
- vector<bool> isFB(count, true);
- for (int i = 0; i < s.size(); i++) {
- if (component_for_v[s[i].first] != component_for_v[s[i].second]) {
- isFB[component_for_v[s[i].first] - 1] = false;
- }
- }
- vector<int> answer;
- for (int i = 0; i < count; i++) {
- if (isFB[i]) {
- for (int j = 0; j < N; j++) {
- if (component_for_v[j] == i + 1) {
- answer.push_back(j);
- }
- }
- }
- }
- cout << answer.size() << endl;
- for (auto& i : answer) {
- cout << i + 1 << endl;
- }
- }
- };
- int main() {
- int n, m;
- cin >> n >> m;
- Graph g(n);
- for (int i = 0; i < m; ++i) {
- int from, to;
- cin >> from >> to;
- g.addEdge(from - 1, to - 1);
- }
- g.solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement