Codeforces gym 101102 K 想法

Topological Sort time limit per test 8 seconds memory limit per test 256 megabytes input standard input output standard output

Consider a directed graph G of N nodes and all edges (u→v) such that u < v. It is clear that this graph doesn’t contain any cycles.

Your task is to find the lexicographically largest topological sort of the graph after removing a given list of edges.

A topological sort of a directed graph is a sequence that contains all nodes from 1 to N in some order such that each node appears in the sequence before all nodes reachable from it.

Input

The first line of input contains a single integer T, the number of test cases.

The first line of each test case contains two integers N and M (1 ≤ N ≤ 105) , the number of nodes and the number of edges to be removed, respectively.

Each of the next M lines contains two integers a and b (1 ≤ a < b ≤ N), and represents an edge that should be removed from the graph.

No edge will appear in the list more than once.

Output

For each test case, print N space-separated integers that represent the lexicographically largest topological sort of the graph after removing the given list of edges.

Example input 3 3 2 1 3 2 3 4 0 4 2 1 2 1 3 output 3 1 2 1 2 3 4 2 3 1 4

题意：给你一个完全图  只有从小标号到大标号的边  删去m条边  求字典序最大的拓扑排序

题解：set搞一搞。。。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<set> #include<vector> using namespace std; struct node{ int num,lab; bool operator <(const node& a)const{ if(num==a.num)return lab>a.lab; return num<a.num; } }edge[100005]; vector<int>sp[100005]; set<node>sps; int der[100005]; int main(){ int t; scanf("%d",&t); while(t--){ int n,m,i,j,x,y; scanf("%d%d",&n,&m); sps.clear(); for(i=1;i<=n;i++){ sp[i].clear(); der[i]=i-1; } for(i=1;i<=m;i++){ scanf("%d%d",&x,&y); sp[x].push_back(y); sp[y].push_back(x); der[y]--; } for(i=1;i<=n;i++){ sps.insert((node){der[i],i}); } for(i=1;i<=n;i++){ node f=*sps.begin(); sps.erase(sps.begin()); printf("%d ",f.lab); for(j=0;j<sp[f.lab].size();j++){ int du=der[sp[f.lab][j]]++; if(sps.erase((node){du,sp[f.lab][j]}))sps.insert((node){du+1,sp[f.lab][j]}); } } printf("\n"); } return 0; }