fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6.  
  7. // Function to calculate the sum of divisors of a number
  8. int sumDiv(int num)
  9. {
  10.     int sum = 0;
  11.     for (int i = 1; i * i <= num; i++)
  12.     {
  13.         if (num % i == 0)
  14.         {
  15.             sum += i;
  16.             if (i != num / i)
  17.             {
  18.                 // Add the complementary divisor
  19.                 sum += num / i;
  20.             }
  21.         }
  22.     }
  23.     return sum;
  24. }
  25.  
  26. unsigned int getFirstSetBitPos(int n)
  27. {
  28.     return log2(n & -n) + 1;
  29. }
  30. // Topological Sort using DFS
  31. void dfs(int v, vector<vector<int>>& adj, vector<bool>& visited, vector<int>& ans)
  32. {
  33.     visited[v] = true;
  34.     for (auto u : adj[v])
  35.     {
  36.         if (!visited[u])
  37.         {
  38.             dfs(u, adj, visited, ans);
  39.         }
  40.     }
  41.     ans.push_back(v); // Add to result after visiting all neighbors
  42. }
  43.  
  44. // Check if there is a cycle in the graph
  45. bool hasCycle(int v, vector<vector<int>>& adj, vector<bool>& visited, vector<bool>& recStack)
  46. {
  47.     visited[v] = true;
  48.     recStack[v] = true;
  49.  
  50.     for (auto u : adj[v])
  51.     {
  52.         if (!visited[u] && hasCycle(u, adj, visited, recStack))
  53.             return true;
  54.         else if (recStack[u]) // If the node is in the recursion stack, cycle is present
  55.             return true;
  56.     }
  57.  
  58.     recStack[v] = false;
  59.     return false;
  60. }
  61.  
  62. // Function to check if the graph is a DAG
  63. bool isDAG(vector<vector<int>>& adj, int n)
  64. {
  65.     vector<bool> visited(n + 1, false), recStack(n + 1, false);
  66.     for (int i = 1; i <= n; ++i)
  67.     {
  68.         if (!visited[i] && hasCycle(i, adj, visited, recStack))
  69.             return false;
  70.     }
  71.     return true;
  72. }
  73.  
  74. // Function to construct the dependency graph
  75. void buildGraph(int n, vector<vector<int>>& adj, int C)
  76. {
  77.     for (int i = 1; i <= n; i++)
  78.     {
  79.         for (int j = 1; j <= n; j++)
  80.         {
  81.             if (i == j) continue;
  82.             if (i % j == 0)
  83.                 adj[i].push_back(j); // i must appear before j
  84.  
  85.  
  86.            else  if (getFirstSetBitPos(i) >getFirstSetBitPos(j))
  87.                 adj[i].push_back(j); // i must appear before j
  88.  
  89.  
  90.         }
  91.     }
  92. }
  93.  
  94. void testcase()
  95. {
  96.     cout << getFirstSetBitPos(6)<<endl;
  97.     int n, C;
  98.     cin >> n >> C;
  99.  
  100.     vector<vector<int>> adj(n + 1);
  101.     buildGraph(n, adj, C);
  102.  
  103.     if (!isDAG(adj, n))
  104.     {
  105.         cout << "Graph contains a cycle. Topological sort not possible.\n";
  106.         return;
  107.     }
  108.  
  109.     // Perform topological sort
  110.     vector<int> res;
  111.     vector<bool> visited(n + 1, false);
  112.     for (int i = 1; i <= n; ++i)
  113.     {
  114.         if (!visited[i])
  115.         {
  116.             dfs(i, adj, visited, res);
  117.         }
  118.     }
  119.  
  120.     reverse(res.begin(), res.end());
  121.  
  122.     // Output the result
  123.     for (auto x : res)
  124.     {
  125.         cout << x << " ";
  126.     }
  127.     cout << endl;
  128. }
  129.  
  130. int main()
  131. {
  132. #ifndef ONLINE_JUDGE
  133.     freopen("input.txt", "r", stdin);
  134.     freopen("output.txt", "w", stdout);
  135. #endif
  136.     speed
  137.  
  138.     int t = 1;
  139.     while (t--)
  140.     {
  141.         testcase();
  142.     }
  143.  
  144.     return 0;
  145. }
  146.  
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/Ocf5Ms
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!