Submission #4060366
Source Code Expand
class UnionFind: def __init__(self, n): self.par = [i for i in range(n+1)] self.rank = [0] * (n+1) # 検索 def find(self, x): if self.par[x] == x: return x else: self.par[x] = self.find(self.par[x]) return self.par[x] # 併合 def union(self, x, y): x = self.find(x) y = self.find(y) if self.rank[x] < self.rank[y]: self.par[x] = y else: self.par[y] = x if self.rank[x] == self.rank[y]: self.rank[x] += 1 # 同じ集合に属するか判定 def same_check(self, x, y): return self.find(x) == self.find(y) def renketu(Town): cnt = 0 for i in range(1,len(Town.par)): for j in range(1,i): if not Town.same_check(i,j): return True return False if __name__ == '__main__': N,M = list(map(int,input().split())) # print(Town.par) bridge = [list(map(int,input().split())) for i in range(M)] cnt = 0 for kesu in range(M): Town = UnionFind(N) for i,(x,y) in enumerate(bridge): if i != kesu: Town.union(x,y) if renketu(Town): cnt += 1 print(cnt)
Submission Info
Submission Time | |
---|---|
Task | C - Bridge |
User | ngs_436 |
Language | Python (3.4.3) |
Score | 300 |
Code Size | 1311 Byte |
Status | AC |
Exec Time | 92 ms |
Memory | 3064 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 300 / 300 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 18 ms | 3064 KB |
sample_02.txt | AC | 18 ms | 3064 KB |
sample_03.txt | AC | 18 ms | 3064 KB |
subtask_1_1.txt | AC | 43 ms | 3064 KB |
subtask_1_10.txt | AC | 20 ms | 3064 KB |
subtask_1_11.txt | AC | 37 ms | 3064 KB |
subtask_1_12.txt | AC | 32 ms | 3064 KB |
subtask_1_13.txt | AC | 32 ms | 3064 KB |
subtask_1_14.txt | AC | 33 ms | 3064 KB |
subtask_1_15.txt | AC | 37 ms | 3064 KB |
subtask_1_16.txt | AC | 39 ms | 3064 KB |
subtask_1_17.txt | AC | 44 ms | 3064 KB |
subtask_1_2.txt | AC | 92 ms | 3064 KB |
subtask_1_3.txt | AC | 28 ms | 3064 KB |
subtask_1_4.txt | AC | 43 ms | 3064 KB |
subtask_1_5.txt | AC | 24 ms | 3064 KB |
subtask_1_6.txt | AC | 39 ms | 3064 KB |
subtask_1_7.txt | AC | 31 ms | 3064 KB |
subtask_1_8.txt | AC | 34 ms | 3064 KB |
subtask_1_9.txt | AC | 19 ms | 3064 KB |