This codes gives correct output in my system but submitting it shows Restricted Function.
Plz help...
**************************************
import Queue
graph={}
dic={}
to_explore=Queue.Queue()
def BFS(root):
    dic[root]=0
    to_explore.put(root)
    while not to_explore.empty():
        tmp=to_explore.get()
        for i in graph[tmp]:
            if i not in dic:
                dic[i]=dic[tmp]+1
                to_explore.put(i)
n=input()
while n:
    s=raw_input().split()
    for i in s:
        if i not in graph:
            graph[i]=[]
            for j in s:
                if j!=i:
                    if j not in graph[i]:
                        graph[i].append(j)
        else:
            for j in s:
                if j!=i:
                    if j not in graph[i]:
                        graph[i].append(j)
    n-=1
if 'Isenbaev' in graph:
    BFS('Isenbaev')
    for i in graph:
        if i not in dic:
            dic[i]='undefined'
    for i in sorted(dic):
        print i,dic[i]
else:
    for i in sorted(graph):
        print i,"undefined"

This case may help you:
2
A B C
B D Isenbaev

ans:
A 2
B 1
C 2
D 1
Isenbaev 0

Hi, I writed this post because I wanted to share with you some of the test cases* that helped me a lot at the time. I hope it helps you :)

--> Test 1:

1
A B C

--> Answer:

A undefined
B undefined
C undefined

------------------------------

--> Test 2:

5
Isenbaev A B
A B C
D Q P
C H N
G N P

--> Answer:

A 1
B 1
C 2
D 5
G 4
H 3
Isenbaev 0
N 3
P 4
Q 5

------------------------------

--> Test 3:

13
Fominykh Isenbaev BBB
BBB CCC AAA
Ayzenshteyn Oparin Samsonov
Ayzenshteyn Chevdar Samsonov
Dublennykh Fominykh Ivankov
Burmistrov Dublennykh Kurpilyanskiy
Cormen Leiserson Rivest
Oparin AA AAA
Isenbaev Oparin Toropov
AA DD PP
PP QQ RR
RR SS TT
TT Toropov Oparin

--> Answer:

AA 2
AAA 2
Ayzenshteyn 2
BBB 1
Burmistrov 3
CCC 2
Chevdar 3
Cormen undefined
DD 3
Dublennykh 2
Fominykh 1
Isenbaev 0
Ivankov 2
Kurpilyanskiy 3
Leiserson undefined
Oparin 1
PP 3
QQ 4
RR 3
Rivest undefined
SS 3
Samsonov 2
TT 2
Toropov 1

------------------------------

--> Test 4:

3
Isenbaev A B
A B C
A Q W

--> Answer:

A 1
B 1
C 2
Isenbaev 0
Q 2
W 2

------------------------------

*(All test cases were made by other users, so you'll probably found them in other Posts/Topics/Discussions).

Acknowledgments to:
-> "Vit Demidenko" & "Nathalie"
-> "Pavel Nikolov"
-> "mccolt89"
-> "Megakrit"


-How I solved it:

I solved this problem in Java, for that, I used:

->1 java.util.Scanner
->1 java.util.HashMap
->1 java.util.TreeMap
->3 java.util.HashSet
->1 java.util.LinkedList
->? java.util.StringTokenizer (or you can just simply use the Scanner method "next()").

(The structures can be declared inside loops or other structures).

Hope all this helped you :)


Edited by author 08.04.2020 00:48

Edited by author 08.04.2020 00:49

What is test 7?

[code deleted]

Edited by moderator 19.11.2019 23:08

can anybody help me with this problem?

Standard BFS question

I can solve it by breadth-first search with Execution time:0.218, but how to solve it with Execution time:0.015 or 0.031??? I have no idea about it. Give me please idea or algorithm's  name to solve it so fast. thank you!

Somebody can give me test case 4?
I don't understand why it's wrong answer...

Edited by author 30.10.2018 11:59

input file:
1
Isenbae Isen Isenbaeva

and, what what is your answer?

Edited by author 25.06.2013 19:22

Edited by author 25.06.2013 19:22

Edited by author 25.06.2013 19:23

I think my idea completely right What's wrong??????


import java.util.Scanner;

public class Main {
    public static void main(String [] args) {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        String s[][] = new String[n][3];
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                s[i][j] = in.next();
            }
        }
        boolean all[][] = new boolean[n][3];
        String ss[][] = new String[3*n][3*n];
        ss[0][0] = "Isenbaev";
        int []index = new int[3*n];
        for(int i=0;i<n;i++){
            index[i] = 0;
        }
        index[0] = 1;
        int d = 1;
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                if(s[i][j].equalsIgnoreCase("Isenbaev"))all[i][j] = true;
            }
        }
        boolean BOR = false;
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                if(s[i][j].equalsIgnoreCase("Isenbaev"))BOR = true;
            }
        }
        for(int q=0;q<3*n;q++){
            boolean bormi = false;
            for(int i=0;i<n;i++){
                boolean bor = false;
                for(int j=0;j<3;j++){
                    for(int t=0;t<index[d-1];t++){
                        if(ss[d-1][t].equalsIgnoreCase(s[i][j])){
                            bor = true;
                            break;
                        }
                    }if(bor)break;
                }
                if(bor){
                    for(int j=0;j<3;j++){
                        if(!all[i][j]){
                            ss[d][index[d]++] = s[i][j];
                            all[i][j]  = true;
                            bormi = true;
                            for(int g=0;g<n;g++){
                                for(int h=0;h<3;h++){
                                    if(s[g][h].equalsIgnoreCase(s[i][j]))all[g][h] = true;
                                }
                            }
                        }
                    }
                }
            }
            if(bormi)d++;
        }
        String []sss = new String[3*n];
        int []son = new int[3*n];
        for(int i=0;i<3*n;i++){
            son[i] = -1;
        }
        int koef = 0;
        for(int i=0;i<d;i++){
            if(i==0){
                if(BOR){
                    BOR = false;
                }else i++;
            }
            for(int j=0;j<index[i];j++){
                sss[koef] = ss[i][j];
                son[koef++] = i;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<3;j++){
                if(!all[i][j]){
                    boolean top = true;
                    for(int p=0;p<koef;p++){
                        if(sss[p].equalsIgnoreCase(ss[i][j]))top = false;
                    }
                    if(top)sss[koef++] = s[i][j];
                }
            }
        }


        n = koef;
        for(int i=0;i<n-1;i++){
            if(sss[i].compareTo(sss[i+1])>0){
                String S = sss[i];
                sss[i] = sss[i+1];
                sss[i+1] = S;
                int SS = son[i];
                son[i] = son[i+1];
                son[i+1] = SS;
                i=-1;
            }
        }

        for(int i=0;i<koef;i++){
            if(son[i]!=-1)System.out.println(sss[i] + " " + son[i]);
            else System.out.println(sss[i] + " undefined" );
        }
    }
}

Edited by author 25.07.2018 00:30

Edited by author 27.07.2018 23:09

What is the test 19?
Help please!

Don't know, what's wrong. Give me tests please.

Create three dictionaries :
    used <boolean>
    connections <set<string>>
    distance <string>

Then import queue.
Then breadth - first search.

Edited by author 30.09.2013 09:17

Edited by author 30.09.2013 09:17

[code deleted]

Edited by moderator 19.11.2019 23:13

Test 3 is RTE
What can I optimise?

n=int(input())
dic={}
for i in range(n):
    team=input().split()
    for x in team:
        if x in dic:
            dic[x].extend((y for y in team if y!=x and y not in dic[x]))
        else:
            dic[x]=[y for y in team if y!=x]
names=sorted(dic.keys())
s='Isenbaev'
level = { s: 0 }
k = 1
frontier = [s]
while frontier:
    next = []
    for u in frontier:
        for v in dic[u]:
            if v not in level:
                level[v] = k
                next.append(v)
    frontier = next
    k += 1
print('\n'.join((x+' '+str(level.get(x, 'undefined')) for x in names)))

Edited by author 09.08.2016 16:37

class Node:
    def __init__(self, name, number):
        self.name = name
        self.number = number
        self.children = []

    def d(self, name):
        for i in self.children:
            if i.name == name:
                self.children.remove(i)
        for i in self.children:
            i.d(name)


def fnc(cmds, item, isenb, root):
    for c in cmds:
        if item.name in c:
            for n in c:
                if not n in isenb:
                    isenb[n] = item.number + 1
                    item.children.append(Node(n, item.number + 1))
                elif isenb[n] > (item.number + 1):
                    isenb[n] = item.number + 1
                    root.d(n)
                    item.children.append(Node(n, item.number + 1))
    for i in item.children:
        fnc(cmds, i, isenb, root)

import sys
if __name__=='__main__':
    n_command = input()
    if(int(n_command) > 0):
        isenb = {}
        cmds = []
        for i in range(0,int(n_command)):
            cmds.append(input().split())
        flag = False
        for c in cmds:
            if "Isenbaev" in c:
                flag = True
                break
        if flag:
            root = Node("Isenbaev", 0)
            isenb["Isenbaev"] = 0
            fnc(cmds, root, isenb, root)
        for c in cmds:
            for i in c:
                if not i in isenb:
                    isenb[i] = "underfined"
        s = ''
        for key,value in sorted(isenb.items()):
            if s == '':
                s += (str(key) + ' ' + str(value))
            else:
                s += ('\n' + str(key) + ' ' + str(value))
        sys.stdout.write(s)
    else:
        sys.stdout.flush()

Why? My solution is ok when i run with other tests that i have seen in this forum, but when i submit here, i get WA#1!

Is there a problem about the output?

Thanks.

BFS (Поиск в ширину).
[code deleted]

Edited by moderator 19.11.2019 23:14