Advertisement
Guest User

Untitled

a guest
Nov 26th, 2014
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN=100;// максимальное число вершин
  7.  
  8. int n; // число вершин
  9. vector<double> g[MAXN]; // граф
  10. bool used[MAXN];
  11. vector<int> order,order1;// ордер
  12.  
  13. void dfs (int v) {
  14. used[v] = true;
  15. for (size_t i=0; i<n; ++i) {
  16. int to = i;
  17. if (!used[i] && g[v][i]!=0)
  18. dfs (i);
  19. }
  20. order.push_back (v);
  21. }
  22.  
  23.  
  24. void main()
  25. {
  26. cin>>n; //общее количество узлов
  27. double k,s;
  28. int ni;
  29. vector<int> d;
  30. cin>>ni; //количестов входных узлов
  31.  
  32. for (int i=0;i<ni;i++){
  33. cin>>s;
  34. d.push_back(s); //небольшой вектор с входными узлами, например:3,4,6 (мы запишем в коносли 2,3,5)
  35. }
  36.  
  37.  
  38. for (int i=0;i<n;i++)
  39. for (int j=0;j<n;j++)
  40. {
  41. cin>>k;
  42. g[i].push_back(k); //заполняем вектор векторов, т.е матрицу смежности
  43. }
  44.  
  45.  
  46. for(int i=0;i<n;i++){
  47. if (!used[i]) // пускаем топологическую сортировку
  48. dfs(i);
  49. }
  50.  
  51. reverse(order.begin(),order.end());//отсортированный топ сортом вектор
  52.  
  53. vector<int> ord(order.size(),0);//вектор, в котором должны будут быть отмечены позиции входных узлов
  54.  
  55. for (int i=0;i<ni;i++)
  56. for (int j=0;j<order.size();j++)
  57. if (d[i]==order[j]) //здесь мы находим в векторе ордер наши входные узлы и помечаем 1 т.е позиции в векторе
  58. ord[j]=1; //на которых они стоят в ордере
  59. //т.е отсортированный топ сортом вектор 5 3 4 2 6 0 7 1, наши входные вершины 2,3,5 находятся на позициях
  60. //3,1,0
  61. for (int i=0;i<ni;i++)
  62. order1.push_back(d[i]); //начинаем заполнять выходной ордер, сначала заполнив входные вершины
  63.  
  64. for (int j=0;j<order.size();j++)
  65. if (ord[j]!=1) //проверяем на помечнность узлы, если они помечены, т.е являются входными вершиными,
  66. order1.push_back(order[j]);//то в вектор их не запихиваем
  67.  
  68. for (int i=0;i<order1.size();i++)
  69. cout<<order1[i]+1<<endl;
  70. system("pause");
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement