daily pastebin goal
49%
SHARE
TWEET

Untitled

a guest Mar 22nd, 2019 85 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. OK, I Understand
 
Top