Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int n, m;
- vector<vector<int>> G(20000);
- vector<vector<int>> GR(20000);
- vector<int> used(20000);
- vector<int> order;
- vector<int> comp;
- void dfs(int v) {
- used[v] = 1;
- for (int i = 0; i < G[v].size(); i++) {
- int actual_v = G[v][i];
- if (used[actual_v] == 0) {
- dfs(actual_v);
- }
- }
- order.push_back(v);
- }
- void dfs_R(int v) {
- used[v] = 1;
- comp.push_back(v);
- for (int i = 0; i < GR[v].size(); i++) {
- int actual_v = GR[v][i];
- if (used[actual_v] == 0) {
- dfs_R(actual_v);
- }
- }
- }
- int main() {
- cin >> n >> m;
- for (int i = 0; i < m; i++) {
- int f, t;
- cin >> f >> t;
- G[f - 1].push_back(t - 1);
- GR[t - 1].push_back(f - 1);
- }
- for (int i = 0; i < n; i++) {
- if (used[i] == 0) {
- dfs(i);
- }
- }
- for (int i = 0; i < n; i++) {
- used[i] = 0;
- }
- int k = 1;
- vector<int> comp_number(n);
- vector<int> comp_v;
- for (int i = 0; i < n; i++) {
- int actual_v = order[n - i - 1];
- if (used[actual_v] == 0) {
- dfs_R(actual_v);
- for (int j = 0; j < comp.size(); j++) {
- comp_number[comp[j]] = k;
- }
- comp_v.push_back(comp[0]);
- k = k + 1;
- comp.clear();
- }
- }
- vector<int> FS(k - 1);
- int st = k;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < G[i].size(); j++) {
- int a = i;
- int b = G[i][j];
- if (comp_number[a] != comp_number[b]) {
- if (FS[comp_number[a] - 1] == 0)
- st = st - 1;
- FS[comp_number[a] - 1] = 1;
- }
- }
- }
- cout << st - 1 << endl;
- for (int i = 0; i < k - 1; i++) {
- if (FS[i] == 0) {
- cout << comp_v[i] + 1 << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment