Problem p03855 (python)

Fixed submission:
N, K, L = map(int, input().split())

def fp(x, parentList): #findParent
    if parentList[x] == x:
        return x
    else:
        parentList[x] = fp(parentList[x], parentList)
        return parentList[x]

#各ノードのparentをリストで表現(連結前は自身がparent)
road = [i for i in range(N)]
rail = [i for i in range(N)]

for _ in range(K):
    p, q = map(int, input().split())
    par_p, par_q = fp(p-1, road), fp(q-1, road) #p, qのparent 
    #連結する際、若い番号をparentとする
    if par_p < par_q:
        road[par_q] = par_p
    else:
        road[par_p] = par_q

#railについても同様
for _ in range(L):
    s, t = map(int, input().split())
    par_s, par_t = fp(s-1, rail), fp(t-1, rail)
    if par_s < par_t:
        rail[par_t] = par_s
    else:
        rail[par_s] = par_t

#連結成分の要素をカウント
cnt = {}
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    if key in cnt:
        cnt[key] += 1
    else:
        cnt[key] = 1
#出力
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    ans = cnt[key]
    print(ans, end=" ")

Buggy submission (verdict: Runtime Error):
N, K, L = map(int, input().split())
#Parent List(PL)
road = [i for i in range(N)]
rail = [i for i in range(N)]

def fp(x,P): #findParent
    if x == P[x]:
        return x
    else:
        P[x] = fp(P[x])
        return P[x]

for i in range(K+L):
    PL = (lambda x:road if x < K else rail)(i)
    p, q = map(lambda x:int(x)-1, input().split())
    p, q = fp(p,PL), fp(q,PL)
    PL[p] = PL[q] = min(p, q)

from collections import defaultdict as dd
Wconnected = dd(lambda:0)
for i in range(N):
    Wconnected[fp(i,road),fp(i,rail)] += 1
print(*[Wconnected[fp(i,road),fp(i,rail)] for i in range(N)])

Buggy submission (verdict: Runtime Error):
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;

long set_index;

void dfs(Graph graph, vector<bool>& seen, vector<int>& set, int v){
    seen[v] = true;
    set[v] = set_index;
    for (auto next_v : graph[v]){
        if (seen[next_v]) continue;
        dfs(graph, seen, set, next_v);
    }
}

void input(Graph& graph, int M){
    int p, q;
    for (int i=0; i<M; i++){
        cin >> p >> q;
        graph[p-1].push_back(q-1);
        graph[q-1].push_back(p-1);
    }
}

void connect(Graph& graph, vector<bool>& seen, vector<int>& set, int n){
    set_index = 0;
    for (int v=0; v<n; v++){
        if (seen[v]) continue;
        dfs(graph, seen, set, v);
        set_index++;
    }
}

int main(){
    int N, K, L;
    cin >> N >> K >> L;
    Graph road, rail;
    vector<bool> seen_road, seen_rail;
    vector<int> set_road, set_rail;
    road.resize(N);
    rail.resize(N);
    set_road.assign(N, 0);
    set_rail.assign(N, 0);
    input(road, K);
    input(rail, L);

    seen_road.assign(N, false);
    connect(road, seen_road, set_road, N);
    seen_rail.assign(N, false);
    connect(rail, seen_rail, set_rail, N);
   
    map<pair<long, long>, int> ans;
    for (int i=0; i<N; i++){
        ans[make_pair(set_road[i],set_rail[i])]++;
    }
    for (int i=0; i<N; i++){
        cout << ans[make_pair(set_road[i],set_rail[i])] << " ";
    }
    return 0;
}

Buggy submission (verdict: Runtime Error):
N, K, L = map(int, input().split())
road = [{"Connected":[],"seen":False,"set":0} for _ in range(N)]
rail = [{"Connected":[],"seen":False,"set":0} for _ in range(N)]

def dfs(graph, v, index): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = index
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, index)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in (road, rail): #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
D = {}
for X in List:
    if not X in D:
        D[X] = 1
    else:
        D[X] += 1
for A in List:
    print(D[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"seen":False,"set":0} for _ in range(200000)]
rail = [{"Connected":[],"seen":False,"set":0} for _ in range(200000)]

def dfs(graph, v, index): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = index
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, index)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in (road, rail): #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
count = collections.Counter(List)
for A in List:
    print(count[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"seen":False,"set":0} for _ in range(N)]
rail = [{"Connected":[],"seen":False,"set":0} for _ in range(N)]

def dfs(graph, v, index): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = index
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, index)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in (road, rail): #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
    del set_index
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
count = collections.Counter(List)
for A in List:
    print(count[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"seen":False,"set":-1} for _ in range(N)]
rail = [{"Connected":[],"seen":False,"set":-1} for _ in range(N)]

def dfs(graph, v, index): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = index
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, index)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in (road, rail): #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
count = collections.Counter(List)
for A in List:
    print(count[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"seen":False} for _ in range(N)]
rail = [{"Connected":[],"seen":False} for _ in range(N)]

def dfs(graph, v, index): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = index
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, index)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in (road, rail): #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
count = collections.Counter(List)
for A in List:
    print(count[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":0,"seen":False} for _ in range(N)]
rail = [{"Connected":[],"set":0,"seen":False} for _ in range(N)]

def dfs(graph, v, num): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = num
    for next_v in set(graph[v]["Connected"]):
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, num)

for X in ((road, K), (rail, L)): #結合を入力
    for _ in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in [road, rail]: #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        dfs(X, v, set_index)
        set_index += 1
        

List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":0,"seen":False} for _ in range(N+1)]
rail = [{"Connected":[],"set":0,"seen":False} for _ in range(N+1)]

def dfs(graph, v, num): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = num
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, num)

for X in ((road, K), (rail, L)): #結合を入力
    for i in range(X[1]):
        p, q = map(int, input().split())
        X[0][p]["Connected"].append(q)
        X[0][q]["Connected"].append(p)

for X in [road, rail]: #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v+1]["seen"]:
            continue
        set_index += 1
        dfs(X, v+1, set_index)
        

List = [(road[i+1]["set"],rail[i+1]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":0,"seen":False} for _ in range(N)]
rail = [{"Connected":[],"set":0,"seen":False} for _ in range(N)]

def dfs(graph, v, num): #深さ優先探索
    graph[v]["seen"] = True
    graph[v]["set"] = num
    for next_v in graph[v]["Connected"]:
        if graph[next_v]["seen"]:
            continue
        dfs(graph, next_v, num)

for X in ((road, K), (rail, L)): #結合を入力
    for i in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(q-1)
        X[0][q-1]["Connected"].append(p-1)

for X in [road, rail]: #探索して連結成分に分解
    set_index = 0
    for v in range(N):
        if X[v]["seen"]:
            continue
        set_index += 1
        dfs(X, v, set_index)
        

List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":0,"seen":False} for _ in range(N)]
rail = [{"Connected":[],"set":0,"seen":False} for _ in range(N)]

def dfs(node, num): #深さ優先探索
    node["seen"] = True
    node["set"] = num
    for next_node in node["Connected"]:
        if next_node["seen"]:
            continue
        dfs(next_node, num)

for X in ((road, K), (rail, L)): #結合を入力
    for i in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(X[0][q-1])
        X[0][q-1]["Connected"].append(X[0][p-1])

for X in [road, rail]: #探索して連結成分に分解
    set_index = 0
    for x in X:
        if x["seen"]:
            continue
        dfs(x, set_index)
        set_index += 1

List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":-1,"seen":False} for i in range(N)]
rail = [{"Connected":[],"set":-1,"seen":False} for i in range(N)]

def dfs(node, num): #深さ優先探索
    node["seen"] = True
    node["set"] = num
    for next_node in node["Connected"]:
        if next_node["seen"]:
            continue
        dfs(next_node, num)

for X in ((road, K), (rail, L)): #結合を入力
    for i in range(X[1]):
        p, q = map(int, input().split())
        X[0][p-1]["Connected"].append(X[0][q-1])
        X[0][q-1]["Connected"].append(X[0][p-1])

for X in [road, rail]: #探索して連結成分に分解
    set_index = 0
    for x in X:
        if x["seen"]:
            continue
        dfs(x, set_index)
        set_index += 1
        
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":-1,"seen":False} for i in range(N)]
rail = [{"Connected":[],"set":-1,"seen":False} for i in range(N)]

def dfs(node, num): #深さ優先探索
    node["seen"] = True
    node["set"] = num
    for next_node in node["Connected"]:
        if next_node["seen"]:
            continue
        dfs(next_node, num)

for i in range(K):
    p, q = map(int, input().split())
    road[p-1]["Connected"].append(road[q-1])
    road[q-1]["Connected"].append(road[p-1])
for i in range(L):
    r, s = map(int, input().split())
    rail[r-1]["Connected"].append(rail[s-1])
    rail[s-1]["Connected"].append(rail[r-1])
for X in [road, rail]: #連結成分に分解
    set_index = 0
    for x in X:
        if x["seen"]:
            continue
        dfs(x, set_index)
        set_index += 1
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
city = [{"road":{"Connected":[],"set":-1,"seen":False},
         "rail":{"Connected":[],"set":-1,"seen":False}} for i in range(N)]

def dfs(graph, v, way, num): #深さ優先探索
    graph[v][way]["seen"] = True
    graph[v][way]["set"] = num
    for next_v in graph[v][way]["Connected"]:
        if graph[next_v][way]["seen"]:
            continue
        dfs(graph, next_v, way, num)

for i in range(K):
    p, q = map(int, input().split())
    city[p-1]["road"]["Connected"].append(q-1)
    city[q-1]["road"]["Connected"].append(p-1)
for i in range(L):
    r, s = map(int, input().split())
    city[r-1]["rail"]["Connected"].append(s-1)
    city[s-1]["rail"]["Connected"].append(r-1)
for X in ["road", "rail"]: #連結成分に分解
    set_index = 0
    for v in range(N):
        if city[v][X]["seen"]:
            continue
        dfs(city, v, X, set_index)
        set_index += 1
List = [(x["road"]["set"],x["rail"]["set"]) for x in city]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
city = [{"road":{"Connected":[i],"set":-1,"seen":False},
         "rail":{"Connected":[i],"set":-1,"seen":False}} for i in range(N)]
def dfs(graph, v, way, num):
    graph[v][way]["seen"] = True
    graph[v][way]["set"] = num
    for next_v in graph[v][way]["Connected"]:
        if graph[next_v][way]["seen"]:
            continue
        dfs(graph, next_v, way, num)

for i in range(K):
    p, q = map(int, input().split())
    city[p-1]["road"]["Connected"].append(q-1)
    city[q-1]["road"]["Connected"].append(p-1)
for i in range(L):
    r, s = map(int, input().split())
    city[r-1]["rail"]["Connected"].append(s-1)
    city[s-1]["rail"]["Connected"].append(r-1)
for X in ["road", "rail"]:
    count = 0
    for v in range(N):
        if city[v][X]["seen"]:
            continue
        dfs(city, v, X, count)
        count += 1
List = [(x["road"]["set"],x["rail"]["set"]) for x in city]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
city = [{"road":{"Connected":[i],"group":-1,"seen":False},
         "rail":{"Connected":[i],"group":-1,"seen":False}} for i in range(N)]
def dfs(graph, v, way, num):
    graph[v][way]["seen"] = True
    graph[v][way]["group"] = num
    for next_v in graph[v][way]["Connected"]:
        if graph[next_v][way]["seen"]:
            continue
        dfs(graph, next_v, way, num)

for i in range(K):
    p, q = map(int, input().split())
    city[p-1]["road"]["Connected"].append(q-1)
    city[q-1]["road"]["Connected"].append(p-1)
for i in range(L):
    r, s = map(int, input().split())
    city[r-1]["rail"]["Connected"].append(s-1)
    city[s-1]["rail"]["Connected"].append(r-1)
for X in ["road", "rail"]:
    count = 0
    for v in range(N):
        if city[v][X]["seen"]:
            continue
        dfs(city, v, X, count)
        count += 1
List = [(city[i]["road"]["group"],city[i]["rail"]["group"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")

Buggy submission (verdict: Runtime Error):
import collections
N, K, L = map(int, input().split())
city = [{"road":{"Connected":[i],"seen":-1}, "rail":{"Connected":[i],"seen":-1}} for i in range(N)]
def dfs(graph, v, way, num):
    graph[v][way]["seen"] = num
    for next_v in graph[v][way]["Connected"]:
        if graph[next_v][way]["seen"] >= 0:
            continue
        dfs(graph, next_v, way, num)

for i in range(K):
    p, q = map(int, input().split())
    city[p-1]["road"]["Connected"].append(q-1)
    city[q-1]["road"]["Connected"].append(p-1)
for i in range(L):
    r, s = map(int, input().split())
    city[r-1]["rail"]["Connected"].append(s-1)
    city[s-1]["rail"]["Connected"].append(r-1)
for X in ["road", "rail"]:
    count = 0
    for v in range(N):
        if city[v][X]["seen"] >= 0:
            continue
        dfs(city, v, X, count)
        count += 1
List = [(city[i]["road"]["seen"],city[i]["rail"]["seen"]) for i in range(N)]
counter = collections.Counter(List)
for i in range(N):
    print(counter[(city[i]["road"]["seen"],city[i]["rail"]["seen"])],end=" ")

Buggy submission (verdict: Runtime Error):
N, K, L = map(int, input().split())
city = [{"road":{"Connected":[i],"seen":False}, "rail":{"Connected":[i],"seen":False}} for i in range(N)]
Connected_Components = {"road":list(),"rail":list()}
def dfs(graph, v, way, List):
    graph[v][way]["seen"] = True
    List.append(v)
    for next_v in graph[v][way]["Connected"]:
        if graph[next_v][way]["seen"] == True:
            continue
        dfs(graph, next_v, way, List)

for i in range(K):
    p, q = map(int, input().split())
    city[p-1]["road"]["Connected"].append(q-1)
    city[q-1]["road"]["Connected"].append(p-1)
for i in range(L):
    r, s = map(int, input().split())
    city[r-1]["rail"]["Connected"].append(s-1)
    city[s-1]["rail"]["Connected"].append(r-1)
for X in ["road", "rail"]:
    count = 0
    for v in range(N):
        if city[v][X]["seen"] == True:
            continue
        Connected_Components[X].append(list())
        dfs(city, v, X, Connected_Components[X][count])
        
        for i in Connected_Components[X][count]:
            city[i][X]["Connected"] = Connected_Components[X][count]
        count += 1
for v in range(N):
    print(len(set(city[v]["road"]["Connected"])&set(city[v]["rail"]["Connected"])), end=" ")

Buggy submission (verdict: Runtime Error):
N, K, L = map(int, input().split())
city = [1 for i in range(N)]
setA = set()
setB = set()
for i in range(K):
    X = set(int(x)-1 for x in input().split())
    for A in setA:
        if A & X != set():
            A = A | X
    else:
        setA.add(X)
for i in range(L):
    Y = set(int(y)-1 for y in input().split())
    for B in setB:
        if B & Y != set():
            B = B | Y
    else:
        setB.add(Y)
for A in setA:
    for B in setB:
        for i in A & B:
            city[i] = len(A&B)
for i in range(N):
    print(city[i], end=" ")