Cod sursa(job #2975941)

Utilizator dumitrache12Dumitrache Iulian dumitrache12 Data 7 februarie 2023 21:16:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include<bits/stdc++.h>
using namespace std;

const int N = 50005;
int n, deg[N];
set<int> req[N];
vector<int> prov[N];
vector<int> sol;
bool visited[N];

ifstream in ("sortaret.in");
ofstream out("sortaret.out");
// auto& in = cin;
// auto& out = cout;

void show()
{
	for(int i=0;i<sol.size();i++)
		out<<sol[i]<<' ';
	out<<endl;
}
void debug()
{	
	for(int i=1;i<=n;i++)
	{
		out<<i<<": ";
		// for(int j=0; j<req[i].size();j++)
		for(auto it=req[i].begin(); it!=req[i].end(); ++it)
			out<<*it<<' ';
		out<<endl;
	}
	
	out<<"sol: ";
	show();
}
void visit(int p)
{
	visited[p] = true;
	sol.push_back(p);
	for(auto el=prov[p].begin(); el!=prov[p].end(); ++el)
	{
		// req[*el].erase(p);
		deg[*el]--;
		// if(req[*el].size() == 0)
		if(deg[*el] == 0)
		{
			// out<<"p: "<<p<<endl;
			// out<<"*el: "<<(*el)<<endl;
			// out<<"req[*el].size(): "<<req[*el].size()<<endl;
			// out<<"deg[*el]: "<<deg[*el]<<endl;
			visit(*el);
		}
		
			
	}
	prov[p].clear();

}
int main(){
	int m, x, y;
	in>>n>>m;
	for(int i=0;i<m;i++)
	{
		in>>x>>y;
		req[y].insert(x);
		deg[y]++;
		prov[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
		// if(req[i].size() == 0)
		if(deg[i]==0)
			if(!visited[i])
				visit(i);
	show();
	
	return 0;
}