toposort

toposort.cpp

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
std::vector<int> g[maxn], ans;
bool vis[maxn];
int indeg[maxn];
int n,m;
void toposort()
{
	queue<int> q;
	for(int i=1;i<=n;i++)
		if(!indeg[i]) q.push(i);
	while(!q.empty())
	{
		int now = q.front();q.pop();
		for(int i=0;i<g[now].size();i++)
		{
			int v = g[now][i];
			indeg[v]--;
			if(!indeg[v]) q.push(v);
		}
		ans.push_back(now);
	}
	if(ans.size()<n) printf("Not a DAG!\n");
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<maxn;i++)
		g[i].clear(), vis[i] = 0;
	for(int i=0;i<m;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		g[u].push_back(v);
		indeg[v]++;
	}
	toposort();
	for(auto x:ans) printf("%d", x);
}

/*
6 8
1 2 1 3 1 4
3 2 3 5
4 5
6 4 6 5

6 1 3 4 2 5


*/