std::vector<int> temp;
it=i;
end=j;
while (it!=end) {
temp.push_back(it);
used[it]=true; //adding to "used vertices" array vertices of current cycle
it=st[it];
}
temp.push_back(it);
cycles.push_back(temp);
}
}
}
}
}
void DFS_VISIT(int u)
{
Graph::Iterator *it;
color[u]=grey;
time++;
d[u]=time;
it = new Graph::Iterator(G,u);
ve++;
int v;
if(it->beg(v))
{
do
{
ed++;
if(color[v]==white)
{
ord[v] = ++cnt; st[v]=u;
p[v]=u;
DFS_VISIT(v);
}
}
while(it->next(v));
}
color[u]=black;
time++;
f[u]=time;
delete it;
}
};
#endif
TSORT.h
#ifndef _Task2
#define _Task2
#include "graph.h"
#include <VECTOR>
#include <QUEUE>
template <class Graph>
class TSORT
{
Graph *G;
int depth,cnt,cntP;
std::vector<int> pre, post;
std::vector<int> in;
std::queue<int> Q;
std::vector<int> obr;
public:
int ve;
int ed;
std::queue<int> Qsort;
TSORT(Graph *G1)
{
G=G1;
ve=ed=0;
}
~TSORT()
{
}
void Do()
{
SortDag();
}
void ToDAG()
{
DFS2();
for(int i=0;i<obr.size()/2;i++)
{
int w=obr[2*i];
int t=obr[2*i+1];
G->Delete(w,t);
G->Insert(t,w);
}
}
private:
void SortDag()
{
in.clear();
for(int u = 0; u < G->V(); u++)
in.push_back(0);
for(u = 0; u < G->V(); u++)
{
int v;
Graph::Iterator A(G,u);
for(A.beg(v);!A.off();A.next(v))
{
in[v]=in[v]+1;
}
}
for(u = 0; u < G->V(); u++)
if(in[u]==0)
Q.push(u);
while(Q.size()>0)
{
u = Q.front();
Q.pop();
int v;
Graph::Iterator A(G,u);
ve++;
for(A.beg(v); !A.off(); A.next(v))
{
ed++;
in[v]=in[v]-1;
if(in[v]==0)
Q.push(v);
}
Qsort.push(u);
}
}
void DFS2()
{
cnt=0;
cntP=0;
pre.clear();
post.clear();
obr.clear();
for(int i=0;i<G->V();i++)
{
pre.push_back(-1);
post.push_back(-1);
}
for(int v=0;v<G->V();v++)
{
if(pre[v]==-1)
{
dfsR2(v,v);
}
}
}
void dfsR2(int v,int w)
{
pre[w] = cnt++;
Graph::Iterator A(G,w);
int t;
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.