Pagini recente » Cod sursa (job #2712319) | Cod sursa (job #2673077) | Cod sursa (job #1326620) | Cod sursa (job #445158) | Cod sursa (job #914684)
Cod sursa(job #914684)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
#include <utility>
using namespace std;
// inline pair<int, int> mp (const int &x, const int &y) {
// pair<int, int> p;
// p.first = x; p.second = y;
// return p;
// }
int main (int argc, char const *argv[])
{
ifstream in ("sortaret.in");
int n, m; in >> n >> m;
vector< vector<int> > liAd(n + 1);
vector<int> gradIntern(n + 1);
int x, y;
while (in >> x >> y) {
liAd[x].push_back(y);
gradIntern[y]++;
}
// set< pair<int, int> > deg;
// for (int i = 1; i <= n; i++) {
// deg.insert( mp(gradIntern[i], i) );
// }
// for (typeof(deg.begin()) it = deg.begin(); it != deg.end(); it++) {
// cout << it->first << ' ' << it->second << '\n';
// }
// for (int i = 1; i <= n; i++) {
// // cout << "int: " << gradIntern[i] << ", ext: " << liAd[i].size() << "; ";
// cout << i << ": ";
// for (unsigned j = 0; j < liAd[i].size(); j++) {
// cout << liAd[i][j] << ' ';
// }
// cout << '\n';
// }
// cout << '\n';
queue<int> coada;
vector<bool> visited(n + 1);
fill (visited.begin(), visited.end(), 0);
for (int i = 1; i <= n; i++) {
if (gradIntern[i] == 0) {
coada.push(i);
visited[i] = true;
}
}
ofstream out ("sortaret.out");
while (!coada.empty()) {
int nod = coada.front();
coada.pop();
out << nod << ' ';
for (unsigned i = 0; i < liAd[nod].size(); i++) {
gradIntern[liAd[nod][i]]--;
if (gradIntern[liAd[nod][i]] == 0 && !visited[liAd[nod][i]]) {
// cout << liAd[nod][i] << '\n';
coada.push(liAd[nod][i]);
visited[liAd[nod][i]] = true;
}
}
}
out.close();
return 0;
}