Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <unordered_set>
- #include <algorithm>
- #include <stack>
- using namespace std;
- class Capcity {
- private:
- void dfs(
- vector<vector<int>>& graph,
- int root,
- vector<int>& indices,
- vector<vector<int>>& sccNodes,
- stack<int>& s,
- stack<int>& p,
- vector<int>& sccMap,
- int& index
- ) {
- // visited
- if (indices[root] >= 0) {
- return;
- }
- indices[root] = index;
- p.push(root);
- s.push(root);
- ++index;
- for (int next : graph[root]) {
- if (indices[next] < 0) {
- dfs(graph, next, indices, sccNodes, s, p, sccMap, index);
- } else if (sccMap[next] < 0) {
- while (indices[p.top()] > indices[next]) {
- p.pop();
- }
- }
- }
- if (root == p.top()) {
- vector<int> component;
- int size = sccNodes.size();
- int top = -1;
- do {
- top = s.top();
- s.pop();
- sccMap[top] = size;
- component.push_back(top);
- } while (top != root);
- p.pop();
- sccNodes.push_back(component);
- }
- }
- public:
- vector<int> pathBased(vector<vector<int>>& graph) {
- int n = graph.size();
- vector<int> indices(n, -1);
- stack<int> s;
- stack<int> p;
- vector<vector<int>> sccNodes;
- vector<int> sccMap(n, -1);
- int index = 0;
- for (int i = 0; i < n; ++i) {
- dfs(graph, i, indices, sccNodes, s, p, sccMap, index);
- }
- int sccN = sccNodes.size();
- vector<int> indegrees(n, 0);
- vector<unordered_set<int>> sccGraph(sccN);
- for (int i = 0; i < n; ++i) {
- int from = sccMap[i];
- for (int x : graph[i]) {
- int to = sccMap[x];
- if (from != to) {
- sccGraph[from].insert(to);
- }
- }
- }
- for (int i = 0; i < sccN; ++i) {
- for (int x : sccGraph[i]) {
- indegrees[x]++;
- }
- }
- int headNode = -1;
- for (int i = 0; i < sccN; ++i) {
- if (indegrees[i] == 0) {
- if (headNode < 0) {
- headNode = i;
- } else {
- headNode = -1;
- break;
- }
- }
- }
- if (headNode == -1) {
- return vector<int>();
- }
- vector<int>& result = sccNodes[headNode];
- sort(result.begin(), result.end());
- return result;
- }
- };
- int main() {
- int n, m;
- cin >> n >> m;
- vector<vector<int>> graph(n);
- for (int i = 0; i < m; ++i) {
- int a, b;
- cin >> a >> b;
- --a;
- --b;
- graph[b].push_back(a);
- }
- vector<int> result = Capcity().pathBased(graph);
- cout << result.size() << endl;
- if (result.empty()) {
- return 0;
- }
- cout << (result[0] + 1);
- for (int i = 1; i < result.size(); ++i) {
- cout << " " << (result[i] + 1);
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement