Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- const int MAXN=100;// максимальное число вершин
- int n; // число вершин
- vector<double> g[MAXN]; // граф
- bool used[MAXN];
- vector<int> order,order1;// ордер
- void dfs (int v) {
- used[v] = true;
- for (size_t i=0; i<n; ++i) {
- int to = i;
- if (!used[i] && g[v][i]!=0)
- dfs (i);
- }
- order.push_back (v);
- }
- void main()
- {
- cin>>n; //общее количество узлов
- double k,s;
- int ni;
- vector<int> d;
- cin>>ni; //количестов входных узлов
- for (int i=0;i<ni;i++){
- cin>>s;
- d.push_back(s); //небольшой вектор с входными узлами, например:3,4,6 (мы запишем в коносли 2,3,5)
- }
- for (int i=0;i<n;i++)
- for (int j=0;j<n;j++)
- {
- cin>>k;
- g[i].push_back(k); //заполняем вектор векторов, т.е матрицу смежности
- }
- for(int i=0;i<n;i++){
- if (!used[i]) // пускаем топологическую сортировку
- dfs(i);
- }
- reverse(order.begin(),order.end());//отсортированный топ сортом вектор
- vector<int> ord(order.size(),0);//вектор, в котором должны будут быть отмечены позиции входных узлов
- for (int i=0;i<ni;i++)
- for (int j=0;j<order.size();j++)
- if (d[i]==order[j]) //здесь мы находим в векторе ордер наши входные узлы и помечаем 1 т.е позиции в векторе
- ord[j]=1; //на которых они стоят в ордере
- //т.е отсортированный топ сортом вектор 5 3 4 2 6 0 7 1, наши входные вершины 2,3,5 находятся на позициях
- //3,1,0
- for (int i=0;i<ni;i++)
- order1.push_back(d[i]); //начинаем заполнять выходной ордер, сначала заполнив входные вершины
- for (int j=0;j<order.size();j++)
- if (ord[j]!=1) //проверяем на помечнность узлы, если они помечены, т.е являются входными вершиными,
- order1.push_back(order[j]);//то в вектор их не запихиваем
- for (int i=0;i<order1.size();i++)
- cout<<order1[i]+1<<endl;
- system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement