为什么我在O(n)中得到TLE?是因为Python吗?请帮帮我,我卡住了图BFS·DFS·Python C++

2024-06-28 19:07:10 发布

您现在位置:Python中文网/ 问答频道 /正文

所以最近我一直在解决很多图形问题,并使用Python来解决问题, 但是每当我用Python甚至C++解决与CordChf或HackerEarth有关的问题时,在每个问题的一些测试案例中,它给出了TLE,我确信我不会超过O(n)。请帮帮我

这样,CodeChef Question 1是基本的BFS,DFS问题,这是^ {A2},很多人告诉我,这是因为Python是一种缓慢的语言,但它对我来说没有意义,因为所有这些竞争性编程站点都认为与P/C++相比,Python代码的5X时间。 有趣的事实是,有许多python解决方案是针对同一个CodeChef Question 1的,我认为他们做了同样的事情,但没有得到TLE,例如,这些Some guy's Solution 1Some guy's solution 2Some guy's solution 3

如果您能告诉我这些家伙的解决方案和我的解决方案有什么区别,或者问题在我的代码中的具体位置(我在哪里花费额外的时间),那将是一个很大的帮助。

在这之后,我尝试用C++实现它,不幸的是,没有魔法发生,它也给了我太多的能量。{a7}

如果您不想转到这些链接:

我的Python解决方案1:

    from collections import defaultdict
from collections import deque
class Graph:

    def __init__ (self):
        self.graph = defaultdict(list)
        self.ll=0
        self.flag=0
        self.visit={}
        self.rp={}
    def creategh(self,a,b):
        try:
            self.rp[(a,b)]+=1
        except:
            self.rp[(a,b)]=1
            if(a!=b):
                self.graph[a].append(b)
    
    def bfs(self,n):
        
        dq = deque([])
        self.ll=0
        dq.appendleft(n)
        self.visit[n]=1

        while(dq):
            s = dq.pop()
            self.ll+=1
            
            for i in self.graph[s]:
                try:
                    self.visit[i] +=1
                    
                except:
                    self.visit[i] = 1
                    
                    dq.appendleft(i)
        return self.ll


g = Graph()



n,m = map(int,input().split())
x=[]
a= list(map(int,input().split()))
x.append(a)
for i in range(len(a)-1):
    if(a[i]==a[i+1]):
        g.creategh((0,i),(0,i+1))
        g.creategh((0,i+1),(0,i))

for i in range(1,n):
    a= list(map(int,input().split()))
    x.append(a)
    for j in range(m):
        
        try:
            if(x[i][min(j+1,m-1)]==x[i][j]):
                g.creategh((i,j),(i,min(j+1,m-1)))
                g.creategh((i,min(j+1,m-1)),(i,j))
        except:
            do="nothing"

        try:
            if(x[max(0,i-1)][j]==x[i][j]):
                g.creategh((max(i-1,0),j),(i,j))
                g.creategh((i,j),(max(i-1,0),j))
        except:
            do="nothing"


        
        

mmx=-999999999999999
mnxm=9999999999999999999999999999999
for i in range(n):
    for j in range(m):
        try:
            g.visit[i]+=1
        except:
            lol=g.bfs((i,j))
            
            if(lol>mmx):
                mmx=lol
                mnxm=x[i][j]

            elif(lol==mmx):
                if(mnxm>x[i][j]):
                    mnxm=x[i][j]
        
    
print(mnxm,mmx)

Tags: inselfforifrangevisit解决方案ll