Int main()

{

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

int n, m, l, r;

cin >> n >> m;

Graf.resize(n), used.resize(n);

forn(i, m)

{

cin >> l >> r;

l--, r--;

Graf[l].push_back(r);

}

forn(i, n)

{

if(!dfs(i))

{

cout << "Cycle";

return 0;

}

used.assign(n, 0);

}

cout << "Normalno";

}

Топологическая сортировка.

Реализация топологической сортировки.

#include <iostream>

#include <sstream>

#include <vector>

#include <algorithm>

#include <string>

using namespace std;

int n;

vector <vector <int>> qq;

vector <bool> used;

vector <int> result;

void dfs(int v){

used[v] = true;

for (int i = 0; i < qq[v].size(); i++)

if(!used[qq[v][i]])

dfs(qq[v][i]);

result.push_back(v);

}

Int main(){

freopen("input.txt","r",stdin);

freopen("output.txt","w",stdout);

int temp;

cin >> n;

cin.get();

qq.resize(n);

used.assign(n, false);

string s;

for(int i = 0; i < n; i++){

std::stringstream ss;

getline(cin, s);

ss << s;

while(ss >> temp){

temp--;

qq[i].push_back(temp);

}

}

for (int i = 0; i < n; i++)

if (!used[i])

dfs (i);

reverse (result.begin(), result.end());

for(int i = 0; i < result.size(); i++)

cout << ++result[i] << " ";

return 0;

}

Алгоритм Флойда.

Реализовать алгоритм Флойда.

#include <iostream>

#include <vector>

#include <sstream>

using namespace std;

const int INF = 1000000000;

Int main(){

freopen ("input.txt","r",stdin);

freopen ("output.txt","w",stdout);

int n; cin >> n;

vector < vector <int> > d(n);

int temp;

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++){

cin >> temp;

if(temp != 0)

d[i].push_back(temp);

else

d[i].push_back(INF);

}

for (int k = 1; k < n; k++)

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

d[i][j] = min (d[i][j], d[i][k] + d[k][j]);

for (int i = 0; i < n; i++, cout << endl)

for (int j = 0; j < n; j++)

cout << d[i][j] <<" ";

return 0;

}

Стек и очередь

Стек.

Создать список из слов. Перестроить элементы списка в обратном порядке.

#include <iostream>

#include <fstream>

#include <stdio.h>

#include <string>

using namespace std;

struct tstack{

string inf;

tstack * next;

};

tstack * head;

tstack *init_stack(){

return NULL;

}

void push_st(tstack *&s, string item){

tstack * r = new tstack;

r->inf = item;

r->next = s;

s=r;

}

string pop_st(tstack *&s){

tstack * r = s;

string i = r->inf;

s = r->next;

delete r;

return i;

}

int empty_stack(tstack *s){

return (s) ? 0: 1;

}

Ifstream in("input.Txt");

ofstream out("output.txt");

Int main(){

string temp;

tstack * head = init_stack();

tstack * head2 = init_stack();

while (in>>temp)

push_st(head, temp);

while (!empty_stack(head)){

temp = pop_st(head);

out<<temp<<" ";

push_st(head2, temp);

}

return 0;

}

Очередь.

Имеется устройство с   последовательными ячейками памяти, работающими по принципу очереди. На вход устройства могут подаваться цифры и символ " * ". При получении цифры устройство размещает её в последней незанятой ячейке памяти. Если все ячейки заняты, первая ячейка освобождается и значения всех остальных смещаются на ячейку влево. Новый элемент (поданная на вход цифра) добавляется в освободившуюся последнюю ячейку. При подаче символа " * " выводится и удаляется элемент из первой ячейки памяти (остальные сдвигаются на освободившуюся ячейку). Если ячейки памяти пусты, печатается сам символ " * ". Промоделируйте работу данного устройства.

#include <fstream>

#include <iostream>

#include <vector>

#include <sstream>

using namespace std;

struct tqueue{

char inf;

tqueue *next;

};

tqueue *head, *tail;

void init_tqueue (tqueue *&h, tqueue *&t)

{h=t=NULL;}

void insert(tqueue *&h, tqueue *&t, char item){

tqueue *r = new tqueue;

r->inf=item; r->next=NULL;

if (!h&&!t)

h=t=r;

else {t->next=r; t=r;}

}

char take(tqueue *&h, tqueue *&t){

tqueue *r=h;

char i=r->inf;

h=r->next;

if (!h)

t=NULL;

delete r;

return i;

}