package main import ( "bufio" "fmt" "os" "strings" ) func main() { yuki1983() } func yuki1983() { // https://yukicoder.me/problems/no/1983 in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n, m, q int fmt.Fscan(in, &n, &m, &q) graph := make([][]Edge, n) edges := make([][2]int, m) for i := 0; i < m; i++ { var u, v int fmt.Fscan(in, &u, &v) u-- v-- graph[u] = append(graph[u], Edge{u, v, 1, i}) graph[v] = append(graph[v], Edge{v, u, 1, i}) edges[i] = [2]int{u, v} } tec := NewTwoEdgeConnectedComponents(graph) tec.Build() uf := NewUnionFindArray(n) for _, e := range edges { from_, to := e[0], e[1] if tec.Get(from_) != tec.Get(to) { uf.Union(from_, to) } } for i := 0; i < q; i++ { var u, v int fmt.Fscan(in, &u, &v) u-- v-- if uf.IsConnected(u, v) { fmt.Fprintln(out, "Yes") } else { fmt.Fprintln(out, "No") } } } type Edge = struct{ from, to, cost, index int } type TwoEdgeConnectedComponents struct { Tree [][]Edge // 缩点后各个顶点形成的树 CompId []int // 每个点所属的边双连通分量的编号 Group [][]int // 每个边双连通分量里的点 g [][]Edge lowLink *LowLink k int } func NewTwoEdgeConnectedComponents(g [][]Edge) *TwoEdgeConnectedComponents { return &TwoEdgeConnectedComponents{ g: g, lowLink: NewLowLink(g), } } func (tec *TwoEdgeConnectedComponents) Build() { tec.lowLink.Build() tec.CompId = make([]int, len(tec.g)) for i := 0; i < len(tec.g); i++ { tec.CompId[i] = -1 } for i := 0; i < len(tec.g); i++ { if tec.CompId[i] == -1 { tec.dfs(i, -1) } } tec.Group = make([][]int, tec.k) for i := 0; i < len(tec.g); i++ { tec.Group[tec.CompId[i]] = append(tec.Group[tec.CompId[i]], i) } tec.Tree = make([][]Edge, tec.k) for _, e := range tec.lowLink.Bridge { tec.Tree[tec.CompId[e.from]] = append(tec.Tree[tec.CompId[e.from]], Edge{tec.CompId[e.from], tec.CompId[e.to], e.cost, e.index}) tec.Tree[tec.CompId[e.to]] = append(tec.Tree[tec.CompId[e.to]], Edge{tec.CompId[e.to], tec.CompId[e.from], e.cost, e.index}) } } // 每个点所属的边双连通分量的编号. func (tec *TwoEdgeConnectedComponents) Get(k int) int { return tec.CompId[k] } func (tec *TwoEdgeConnectedComponents) dfs(idx, par int) { if par >= 0 && tec.lowLink.ord[par] >= tec.lowLink.low[idx] { tec.CompId[idx] = tec.CompId[par] } else { tec.CompId[idx] = tec.k tec.k++ } for _, e := range tec.g[idx] { if tec.CompId[e.to] == -1 { tec.dfs(e.to, idx) } } } type LowLink struct { Articulation []int // 関節点 Bridge []Edge // 橋 g [][]Edge ord, low []int used []bool } func NewLowLink(g [][]Edge) *LowLink { return &LowLink{g: g} } func (ll *LowLink) Build() { ll.used = make([]bool, len(ll.g)) ll.ord = make([]int, len(ll.g)) ll.low = make([]int, len(ll.g)) k := 0 for i := 0; i < len(ll.g); i++ { if !ll.used[i] { k = ll.dfs(i, k, -1) } } } func (ll *LowLink) dfs(idx, k, par int) int { ll.used[idx] = true ll.ord[idx] = k k++ ll.low[idx] = ll.ord[idx] isArticulation := false beet := false cnt := 0 for _, e := range ll.g[idx] { if e.to == par { tmp := beet beet = true if !tmp { continue } } if !ll.used[e.to] { cnt++ k = ll.dfs(e.to, k, idx) ll.low[idx] = min(ll.low[idx], ll.low[e.to]) if par >= 0 && ll.low[e.to] >= ll.ord[idx] { isArticulation = true } if ll.ord[idx] < ll.low[e.to] { ll.Bridge = append(ll.Bridge, e) } } else { ll.low[idx] = min(ll.low[idx], ll.ord[e.to]) } } if par == -1 && cnt > 1 { isArticulation = true } if isArticulation { ll.Articulation = append(ll.Articulation, idx) } return k } func min(a, b int) int { if a < b { return a } return b } func NewUnionFindArray(n int) *UnionFindArray { parent, rank := make([]int, n), make([]int, n) for i := 0; i < n; i++ { parent[i] = i rank[i] = 1 } return &UnionFindArray{ Part: n, rank: rank, n: n, parent: parent, } } type UnionFindArray struct { // 连通分量的个数 Part int rank []int n int parent []int } func (ufa *UnionFindArray) Union(key1, key2 int) bool { root1, root2 := ufa.Find(key1), ufa.Find(key2) if root1 == root2 { return false } if ufa.rank[root1] > ufa.rank[root2] { root1, root2 = root2, root1 } ufa.parent[root1] = root2 ufa.rank[root2] += ufa.rank[root1] ufa.Part-- return true } func (ufa *UnionFindArray) UnionWithCallback(key1, key2 int, cb func(big, small int)) bool { root1, root2 := ufa.Find(key1), ufa.Find(key2) if root1 == root2 { return false } if ufa.rank[root1] > ufa.rank[root2] { root1, root2 = root2, root1 } ufa.parent[root1] = root2 ufa.rank[root2] += ufa.rank[root1] ufa.Part-- cb(root2, root1) return true } func (ufa *UnionFindArray) Find(key int) int { for ufa.parent[key] != key { ufa.parent[key] = ufa.parent[ufa.parent[key]] key = ufa.parent[key] } return key } func (ufa *UnionFindArray) IsConnected(key1, key2 int) bool { return ufa.Find(key1) == ufa.Find(key2) } func (ufa *UnionFindArray) GetGroups() map[int][]int { groups := make(map[int][]int) for i := 0; i < ufa.n; i++ { root := ufa.Find(i) groups[root] = append(groups[root], i) } return groups } func (ufa *UnionFindArray) Size(key int) int { return ufa.rank[ufa.Find(key)] } func (ufa *UnionFindArray) String() string { sb := []string{"UnionFindArray:"} for root, member := range ufa.GetGroups() { cur := fmt.Sprintf("%d: %v", root, member) sb = append(sb, cur) } sb = append(sb, fmt.Sprintf("Part: %d", ufa.Part)) return strings.Join(sb, "\n") }