fork download
copy 
  1. import sys
  2. sys.setrecursionlimit(1000005)
  3.  
  4. def bipartite(adj, color, source):
  5.  
  6.     if visited[source] == 0:
  7.         visited[source] = color
  8.         if color == 1: color = 2
  9.         else: color = 1
  10.  
  11.         for v in adj[source]:
  12.  
  13.             if visited[v] == 0:
  14.                 if bipartite(adj, color, v) == -1:
  15.                 	return -1
  16.             elif visited[v] == visited[source]:
  17.                 #print 'not bipartite'
  18.                 return -1
  19.  
  20.  
  21.  
  22. for i in xrange(1,int(raw_input())+1):
  23.     p,q = map(int, raw_input().split())
  24.     global visited
  25.     flag = True
  26.     visited = [0]*p
  27.     adj = {}
  28.     for x in range(p): adj[x] = []
  29.     for _ in xrange(q):
  30.         m,n = map(int, raw_input().split())
  31.         adj[m-1].append(n-1)
  32.         adj[n-1].append(m-1)
  33.  
  34.  
  35.     print 'Scenario #%i:'% i
  36.     for source in range(p):
  37.         if visited[source] == 0:
  38.             if bipartite(adj, 1, source) == -1:
  39.                 print 'Suspicious bugs found!'
  40.                 flag = False
  41.                 break
  42.     if flag:
  43.         print 'No suspicious bugs found!'
  44.  
Success #stdin #stdout 0.02s 44680KB
comments (?)
stdin
copy 
2
3 3
1 2
2 3
1 3
4 2
1 2
3 4
stdout
copy 
Scenario #1:
Suspicious bugs found!
Scenario #2:
No suspicious bugs found!
https://ideone.com/By2nVd
language:
Python (PyPy 2.7.13)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!