• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Mar 22nd, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <unordered_set>
4. #include <algorithm>
5. #include <stack>
6.
7. using namespace std;
8.
9. class Capcity {
10. private:
11.   void dfs(
12.     vector<vector<int>>& graph,
13.     int root,
14.     vector<int>& indices,
15.     vector<vector<int>>& sccNodes,
16.     stack<int>& s,
17.     stack<int>& p,
18.     vector<int>& sccMap,
19.     int& index
20.   ) {
21.     // visited
22.     if (indices[root] >= 0) {
23.       return;
24.     }
25.     indices[root] = index;
26.     p.push(root);
27.     s.push(root);
28.     ++index;
29.     for (int next : graph[root]) {
30.       if (indices[next] < 0) {
31.         dfs(graph, next, indices, sccNodes, s, p, sccMap, index);
32.       } else if (sccMap[next] < 0) {
33.         while (indices[p.top()] > indices[next]) {
34.           p.pop();
35.         }
36.       }
37.     }
38.     if (root == p.top()) {
39.       vector<int> component;
40.       int size = sccNodes.size();
41.       int top = -1;
42.       do {
43.         top = s.top();
44.         s.pop();
45.         sccMap[top] = size;
46.         component.push_back(top);
47.       } while (top != root);
48.       p.pop();
49.       sccNodes.push_back(component);
50.     }
51.   }
52. public:
53.   vector<int> pathBased(vector<vector<int>>& graph) {
54.     int n = graph.size();
55.     vector<int> indices(n, -1);
56.     stack<int> s;
57.     stack<int> p;
58.     vector<vector<int>> sccNodes;
59.     vector<int> sccMap(n, -1);
60.
61.     int index = 0;
62.     for (int i = 0; i < n; ++i) {
63.       dfs(graph, i, indices, sccNodes, s, p, sccMap, index);
64.     }
65.     int sccN = sccNodes.size();
66.
67.     vector<int> indegrees(n, 0);
68.
69.     vector<unordered_set<int>> sccGraph(sccN);
70.     for (int i = 0; i < n; ++i) {
71.       int from = sccMap[i];
72.       for (int x : graph[i]) {
73.         int to = sccMap[x];
74.         if (from != to) {
75.           sccGraph[from].insert(to);
76.         }
77.       }
78.     }
79.
80.     for (int i = 0; i < sccN; ++i) {
81.       for (int x : sccGraph[i]) {
82.         indegrees[x]++;
83.       }
84.     }
85.
86.     int headNode = -1;
87.     for (int i = 0; i < sccN; ++i) {
88.       if (indegrees[i] == 0) {
89.         if (headNode < 0) {
90.           headNode = i;
91.         } else {
92.           headNode = -1;
93.           break;
94.         }
95.       }
96.     }
97.
98.     if (headNode == -1) {
99.       return vector<int>();
100.     }
101.     vector<int>& result = sccNodes[headNode];
102.     sort(result.begin(), result.end());
103.     return result;
104.   }
105. };
106.
107. int main() {
108.   int n, m;
109.   cin >> n >> m;
110.   vector<vector<int>> graph(n);
111.   for (int i = 0; i < m; ++i) {
112.     int a, b;
113.     cin >> a >> b;
114.     --a;
115.     --b;
116.     graph[b].push_back(a);
117.   }
118.   vector<int> result = Capcity().pathBased(graph);
119.   cout << result.size() << endl;
120.   if (result.empty()) {
121.     return 0;
122.   }
123.   cout << (result[0] + 1);
124.   for (int i = 1; i < result.size(); ++i) {
125.     cout << " " << (result[i] + 1);
126.   }
127.   cout << endl;
128.   return 0;
129. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top