Pagini recente » Cod sursa (job #620652) | Cod sursa (job #1569951) | Cod sursa (job #524059) | Infoarena Monthly 2014 - Runda 1 | Cod sursa (job #784189)
Cod sursa(job #784189)
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <vector>
using namespace std;
char** read(fstream& f, int& n, int& m, vector<int> °)
{
int i, val1, val2;
char **a;
f >> n >> m;
deg.resize(n+1);
a = new char*[n+1];
for (i = 1; i <= n; i++)
a[i] = new char[n+1];
for (i = 0; i < m; i++) {
f >> val1 >> val2;
a[val1][val2] = 1;
deg[val2]++;
}
return a;
}
list<int> toposort(char **a, int n, vector<int> deg)
{
list<int> l;
queue<int> q;
int i, node;
for (i = 1; i <= n; i++)
if (deg[i] == 0)
q.push(i);
while (!q.empty()) {
node = q.front();
q.pop();
l.push_back(node);
for (i = 1; i <= n; i++)
if (a[node][i] == 1) {
a[node][i] = 0;
deg[i]--;
if (!deg[i])
q.push(i);
}
}
return l;
}
void print(fstream& g, list<int> l)
{
while(!l.empty()) {
g << l.front() << " ";
l.pop_front();
}
}
void discard(char **a, int n)
{
int i;
for (i = 0; i < n+1; i++)
delete[] a[i];
delete[] a;
}
int main(void)
{
fstream f("sortaret.in", ios::in), g("sortaret.out", ios::out);
int n, m;
char **a;
vector<int> deg;
list<int> l;
a = read(f, n, m, deg);
/*for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++)
cout << a[i][j] << " ";
cout << endl;
}*/
l = toposort(a, n, deg);
print(g, l);
discard(a, n);
f.close();
g.close();
return 0;
}