-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathC.kt
92 lines (75 loc) · 2.05 KB
/
C.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.lang.AssertionError
private val input = System.`in`.bufferedReader()
private val output = StringBuilder()
private fun readLn() = input.readLine()!! // string line
private fun readInt() = readLn().toInt() // single int
private fun readLong() = readLn().toLong() // single long
private fun readDouble() = readLn().toDouble() // single double
private fun readStrings() = readLn().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints
private fun readLongs() = readStrings().map { it.toLong() } // list of longs
private fun readDoubles() = readStrings().map { it.toDouble() } // list of doubles
private fun myAssert(x: Boolean) {
if (!x) {
throw AssertionError()
}
}
private const val maxN: Int = 500000+10
private val adj: MutableList<MutableList<Int>> = mutableListOf()
private val vis: MutableList<Boolean> = mutableListOf()
private val friends: MutableList<Int> = mutableListOf()
private fun init(n: Int) {
for (i in 1..n) {
adj[i].clear()
vis[i] = false
}
}
private fun dfs(node: Int) {
vis[node] = true
friends.add(node)
for(child in adj[node]) {
if(!vis[child]) {
dfs(child)
}
}
}
private fun runCase() {
var(n, m) = readInts()
init(n)
repeat(m) {
var tmp = readInts()
if(tmp.size != 2) {
for( i in 1 until tmp.size - 1) {
var u = tmp[i]
var v = tmp[i + 1]
adj[u].add(v)
adj[v].add(u)
}
}
}
var ans = IntArray(n + 1)
for(i in 1..n) {
if(!vis[i]) {
friends.clear()
dfs(i)
for(friend in friends) {
ans[friend] = friends.size
}
}
}
for (i in 1..n) {
output.append("${ans[i]} ")
}
}
fun main(args: Array<String>) {
var t: Int = 1
// t = readInt()
for(i in 0 until maxN) {
adj.add(mutableListOf())
vis.add(false)
}
repeat(t) {
runCase()
}
print(output)
}