Pagini recente » Cod sursa (job #2764765) | Cod sursa (job #2127648) | Cod sursa (job #2325519) | Cod sursa (job #1609824) | Cod sursa (job #2445906)
#include <bits/stdc++.h>
using namespace std;
class graphTopologicalSort
{
private:
#define uint unsigned int
#define pb push_back
#define G_TOPOLOGICAL_SORT_CHECK_CREATED(ret) if (!created) return ret
#define G_TOPOLOGICAL_SORT_CIRCUIT 2
#define G_TOPOLOGICAL_SORT_OK 1
#define G_TOPOLOGICAL_SORT_ERROR 3
bool created;
std::vector<uint>*g;
uint *di, *dc, n;
public:
graphTopologicalSort(): g(nullptr), di(nullptr), dc(nullptr), created(false){}
bool create(uint sz)
{
if (created) return false;
g = new std::vector<uint>[sz + 2];
if (g == nullptr) return false;
di = new uint[sz + 2];
if (di == nullptr)
{
delete[] g;
return false;
}
dc = new uint[sz + 2];
if (dc == nullptr)
{
delete[] g;
delete[] di;
return false;
}
n = sz;
for (uint i=0;i<sz + 2;++i)
di[i] = dc[i] = 0;
created = true;
return true;
}
bool addEdge(uint x, uint y)
{
G_TOPOLOGICAL_SORT_CHECK_CREATED(false);
if (x > n || y > n) return false;
g[x].pb(y);
++di[y];
return true;
}
uint topologicalSort(std::vector<uint> &top)
{
G_TOPOLOGICAL_SORT_CHECK_CREATED(G_TOPOLOGICAL_SORT_ERROR);
top.clear();
std::queue<uint>q;
for (uint i=1;i<=n;++i)
{
dc[i] = di[i];
if (!dc[i])
q.push(i);
}
uint nodes = 0, act;
while (!q.empty())
{
act = q.front();
++nodes;
top.pb(act);
q.pop();
for (uint i=0;i<g[act].size();++i)
{
--dc[g[act][i]];
if (!dc[g[act][i]])
q.push(g[act][i]);
}
}
if (nodes < n) return G_TOPOLOGICAL_SORT_CIRCUIT;
return G_TOPOLOGICAL_SORT_OK;
}
};
int main()
{
int n, m, x, y;
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
scanf("%d %d",&n,&m);
graphTopologicalSort topp;
topp.create(n);
for (int i=1;i<=m;++i)
{
scanf("%d %d",&x,&y);
topp.addEdge(x, y);
}
vector<unsigned int>ans;
topp.topologicalSort(ans);
for (auto x:ans)
printf("%d ", x);
printf("\n");
return 0;
}