大佬们好,我想知道我这个思想的漏洞在哪里? 我先将每个节点的限制用优先队列从小到大排序,然后从小到大遍历节点,如果当前遍历的节点有限制(优先队列不为空),则对其进行深度优先遍历。直到队列为空后,将该值输出。如果深度超过节点数,则视为限制出现环,则输出Impossible。只有10分。
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int D;
int N , M;
struct In
{
int a;
bool operator < (const In b)const
{
return a > b.a;
}
};
struct Node
{
int pos;
priority_queue<In> Q;
Node()
{
}
};
void solution(int pos , Node node[] , int , int []);
const int MaxSize = 1e7 + 7;
int bi = 0;
int cnt[MaxSize];
bool flag ;
int main()
{
cin>>D;
while(D--)
{
cin>>N>>M;
Node node[N + 1];
flag = true;
bi = 0;
int vis[N + 1];
for(int i = 1; i <= N ; i++)
{
node[i].pos = i;
vis[i] = 0;
cnt[i] = 0;
}
for(int i = 0 ; i < M ; i++)
{
int a ,b;
cin>>a>>b;
if(a == b)
{
continue;
}
In in;
in.a = a;
node[b].Q.push(in);
}
for(int i = 1 ; i <= N ; i++)
{
solution(i , node , 0 , vis);
}
if(flag)
{
for(int i = 0 ; i < N ; i++)
{
cout<<cnt[i]<<" ";
}
cout<<endl;
}
else
{
cout<<"Impossible!"<<endl;
}
}
return 0;
}
void solution(int pos , Node node[] , int times , int vis[])
{
if(times > N )
{
flag = false;
return ;
}
if( vis[pos] )return ;
priority_queue<In> Q;
Q = node[pos].Q;
while( !Q.empty() )
{
In in = Q.top();
Q.pop();
if( vis[in.a] )
{
continue;
}
if( !node[in.a].Q.empty() )
solution(in.a , node , times + 1 , vis);
else
{
cnt[bi++] = in.a;
vis[in.a] = 1;
}
}
cnt[bi++] = pos;
vis[ pos ] = 1;
}