Pagini recente » Cod sursa (job #1249803) | Cod sursa (job #2673104) | Cod sursa (job #784701) | Cod sursa (job #895826) | Cod sursa (job #690526)
Cod sursa(job #690526)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
using namespace std;
int N, M;
set< pair<int, int> > values;
vector<int> Start;
vector< vector<int> > listAd;
vector<bool> visited;
ofstream out ("sortaret.out");
void dfs (int nod)
{
out << nod << ' ';
int k = Start[nod];
visited[nod] = true;
vector<int> order;
while (k)
{
if (!visited[listAd[0][k]])
{
order.push_back(listAd[0][k]);
//dfs(listAd[0][k]);
}
k = listAd[1][k];
}
sort(order.begin(), order.end());
for (unsigned i = 0; i < order.size(); i++)
dfs (order[i]);
}
int main (int argc, char const *argv[])
{
ifstream in ("sortaret.in");
in >> N >> M;
Start.resize(N + 1);
for (int i = 1; i <= M; i++)
{
int from, to; in >> from >> to;
values.insert (make_pair(from, to));
}
int count = 1;
M = values.size();
listAd.resize(2, vector<int>(M + 1));
for (typeof(values.begin()) it = values.begin(); it != values.end(); it++)
{
// cout << (*it).first << ' ' << (*it).second << '\n';
listAd[0][count] = (*it).second;
listAd[1][count] = Start[(*it).first];
Start[(*it).first] = count;
count++;
}
/*
for (int i = 1; i <= N; i++)
cout << Start[i] << ' ';
cout << '\n';
for (int i = 1; i <= M; i++)
{
cout << i << ": " << listAd[0][i] << ' ' << listAd[1][i] << '\n';
}
cout << '\n';
*/
visited.resize(N + 1);
for (int i = 1; i <= N; i++)
{
if (!visited[i])
dfs(i);
}
out.close();
return 0;
}