DFS的思路有什么问题么?
查看原帖
DFS的思路有什么问题么?
636095
zhangbaoxin楼主2023/3/29 21:16

大佬们好,我想知道我这个思想的漏洞在哪里? 我先将每个节点的限制用优先队列从小到大排序,然后从小到大遍历节点,如果当前遍历的节点有限制(优先队列不为空),则对其进行深度优先遍历。直到队列为空后,将该值输出。如果深度超过节点数,则视为限制出现环,则输出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;

}

2023/3/29 21:16
加载中...