输入描述:
输入第行为一个正整数T (T <= 10)， 表示有T组数据。
每组数据第一行，输入两个正整数N，M(1
输出描述:
对于每组数据，如果能唯一确定比赛排名， 则输出比赛排名。否则输出NO
输入示例
4
3 2
2 1 3
2 1 2
4 3
3 1 2 3
2 1 3
2 1 4
4 1
4 1 2 3 4
4 3
3 1 2 4
3 1 3 4
2 3 2
输出示例
NO
NO
1 2 3 4
1 3 2 4
#include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>
using namespace std;
void solve(){
int N,M,C;
cin>>N>>M;
vector<unordered_set<int>> child(N+1),parent(N+1);
while(M--){
cin>>C;
int pre=-1,x;
while(C--){
cin>>x;
if(pre!=-1){
child[pre].insert(x);
parent[x].insert(pre);
}
pre=x;
}
}
//寻找最开始的元素
vector<int> index(N+1);
queue<int> q;
for(int i=1;i<=N;i++){
index[i]=parent[i].size();
if(index[i]==0){
q.push(i);
}
}
//依次寻找元素
vector<int> ans;
while(!q.empty()){
if(q.size()!=1) break; //判断是否唯一
int u=q.front();
ans.push_back(u);
q.pop();
while(!child[u].empty()){
int v=*child[u].begin(); //依次寻找
if(--index[v]==0){ //index[v] ，v前有多人，证明u不是前面一个，减一
q.push(v);
}
child[u].erase(v);
}
}
if(ans.size()!=N){
cout<<"NO"<<endl;
}else{
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<' ';
}
cout<<endl;
}
}
int main()
{
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
