Problem: You are given an undirected graph consisting of N vertices and M edges. The vertices are numbered 1 to N, and the edges are numbered 1 to M. In addition, each vertex has a label, `A` or `B`. The label of Vertex i is s_i. Edge i bidirectionally connects vertex a_i and b_i.  The phantom thief Nusook likes to choose some vertex as the startpoint and traverse an edge zero or more times. Today, he will make a string after traveling as above, by placing the labels of the visited vertices in the order visited, beginning from the startpoint.  For example, in a graph where Vertex 1 has the label `A` and Vertex 2 has the label `B`, if Nusook travels along the path 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 2, the resulting string is `ABABB`.  Determine if Nusook can make all strings consisting of `A` and `B`.

Submission attempts (in order):
#! /usr/bin/env python
# -*- coding: utf-8 -*-

#

"""
GC027 C
"""

n,m = map(int,input().split())
s = list(input())
edges = [tuple(map(int,input().split())) for i in range(m)]
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]


def addEdge(graph,u,v):
    graph[u].add(v)


from collections import defaultdict
graphAB = defaultdict(set)

def incrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]+=1
    if s[adj-1] == 'B':
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]-=1
    if s[adj-1] == 'B':
        bli[node-1]-=1

for i,j in edges:
    addEdge(graphAB,i,j)
    addEdge(graphAB,j,i)

def adjAB(node):
    if ali[node-1]!=0 and bli[node-1]!=0:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 'C'
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)


while bool(visitset):
    
    #print(graphABopp)
    #print(abli)
    i = visitset.pop()
    for j in graphAB[i]:
        if s[j-1] != 'C':
            decrementAB(j,i)
            if not adjAB(j):
                visitset.add(j)
    s[i-1] = 'C'


#print(graphABopp)


if bool(set(s).remove('C')):
    print('Yes')
else:
    print('No')






n,m = map(int,input().split())
s = list(input())
edges = [tuple(map(int,input().split())) for i in range(m)]


edgeset = set()
for i,j in edges:
    edgeset.add((min(i,j),max(i,j)))


def addEdge(graph,u,v):
    graph[u].add(v)


def deleteNode(graph,node):
    graph.pop(node,None)

from collections import defaultdict
graphAB = defaultdict(set)
graphABopp = defaultdict(set)

for i,j in edgeset:
    addEdge(graphAB,i,j)
    addEdge(graphABopp,j,i)

abli = [[0,0] for i in range(n)]

def incrimentAB(j,char):
    if char == 'A':
        abli[j-1][0] += 1
    if char =='B':
        abli[j-1][1] += 1

def decrimentAB(j,char):
    if char == 'A':
        abli[j-1][0] -= 1
    if char =='B':
        abli[j-1][1] -= 1


def adjAB(node):
    if abli[node-1][0] != 0 and abli[node-1][1] != 0:
        return(True)
    else:
        return(False)

for i,j in edgeset:
    incrimentAB(j,s[i-1])
    incrimentAB(i,s[j-1])



visitset = set([i for i in set(graphAB.keys())|set(graphABopp.keys()) if not adjAB(i)])
deleteset = set()
print(visitset)

while bool(visitset):
    i = visitset.pop()
    deleteset.add(i)
    for j in graphAB[i]:
        decrimentAB(j,s[i-1])
        graphABopp[j].remove(i)
        if not adjAB(j):
            visitset.add(j)
            print(visitset,'add')
    for j in graphABopp[i]:
        decrimentAB(j,s[i-1])
        graphAB[j].remove(i)
        if not adjAB(j):
            visitset.add(j)
            print(visitset,'add')
    graphAB.pop(i,None)
    graphABopp.pop(i,None)

print(graphAB)
print(graphABopp)


if graphAB == {} and graphABopp == {}:
    print('No')
else:
    print('Yes')






n,m = map(int,input().split())
s = list(input())
abli = [tuple(map(int,input().split())) for i in range(m)]

def addEdge(graph,u,v):
    graph[u].append(v)


def adjAB(graph,node):
    Aflag =False
    Bflag =False
    for i in graph[node]:
        if s[i-1]=='A':
            Aflag = True
        if s[i-1]=='B':
            Bflag = True
        if Aflag and Bflag:
            break
    if Aflag and Bflag:
        return(True)
    else:
        return(False)


def deleteNode(graph,node,s):
    graph.pop(node,None)
    s[node-1]='C'
    print(s)
        


from collections import defaultdict
graphAB = defaultdict(list)

for i,j in abli:
    addEdge(graphAB,i,j)
    if i != j:
        addEdge(graphAB,j,i)


flag = True

while flag:
    flag = False
    deletelist = []
    for i in graphAB:
        if not adjAB(graphAB,i):
            deletelist.append(i)
            flag = True
    for i in deletelist:
        deleteNode(graphAB,i,s)

print(graphAB)

if graphAB == {}:
    print('No')
else:
    print('Yes')





n,m = map(int,input().split())
s = list(input())
abli = [tuple(map(int,input().split())) for i in range(m)]

def addEdge(graph,u,v):
    graph[u].append(v)


def adjAB(graph,node):
    Aflag =False
    Bflag =False
    for i in graph[node]:
        if s[i-1]=='A':
            Aflag = True
        if s[i-1]=='B':
            Bflag = True
        if Aflag and Bflag:
            break
    if Aflag and Bflag:
        return(True)
    else:
        return(False)


def deleteNode(graph,node):
    graph.pop(node,None)
    s[node-1] = 'C'
        


from collections import defaultdict
graphAB = defaultdict(list)

for i,j in abli:
    addEdge(graphAB,i,j)
    if i != j:
        addEdge(graphAB,j,i)


visitset = set(graphAB.keys())
deleteset=set()

while bool(visitset):
    i = visitset.pop()
    print(i,visitset)
    if not adjAB(graphAB,i):
        deleteset.add(i)
        print(i)
        tmp = set(graphAB[i])
        visitset = (visitset | tmp) - deleteset
        deleteNode(graphAB,i)




if graphAB == {}:
    print('No')
else:
    print('Yes')






n,m = map(int,input().split())
s = list(input())
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]

for i in range(m):
    u,v=map(int,input().split())
    graphAB[u].append(v)
    graphAB[v].append(u)


from collections import defaultdict
graphAB = defaultdict(list)

def incrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]+=1
    if s[adj-1] == 'B':
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]-=1
    if s[adj-1] == 'B':
        bli[node-1]-=1


def adjAB(node):
    if ali[node-1]!=0 and bli[node-1]!=0:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 'C'
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)


while bool(visitset):
    
    #print(graphABopp)
    #print(abli)
    i = visitset.pop()
    gen = (j for j in graphAB[i] if s[j-1]!='C')
    for j in gen
        decrementAB(j,i)
        if not adjAB(j):
            visitset.add(j)
    s[i-1] = 'C'


#print(graphABopp)

sset= set(s)
sset.add('C')
sset.remove('C')
if bool(sset):
    print('Yes')
else:
    print('No')





#! /usr/bin/env python
# -*- coding: utf-8 -*-

#

"""
GC027 C
"""

n,m = map(int,input().split())
s = bytes(input(),'utf-8')
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]
import array as ar
remain = ar.array('b',[1 for i in range(n)])
from collections import defaultdict
graphAB = defaultdict(list)

for i in range(m):
    u,v=map(int,input().split())
    graphAB[u].append(v)
    graphAB[v].append(u)



def incrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]+=1
    if s[adj-1] == 66:
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 65:
        ali[node-1]-=1
    if s[adj-1] == 66:
        bli[node-1]-=1


def adjAB(node):
    if ali[node-1] and bli[node-1]:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        remain[i-1] = 0
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)
            remain[i-1] = 0

#print(s)
while bool(visitset):
    i = visitset.pop()
    for j in filter(lambda x:remain[x-1],graphAB[i]):
        #print('loop')
        decrementAB(j,i)
        if not adjAB(j):
            visitset.add(j)
            remain[j-1] = 0

if set(remain)=={0}:
    print('No')
else:
    print('Yes')





Verdicts: Runtime Error

Wrong Answer

Runtime Error

Wrong Answer

Runtime Error

Accepted