Graph Representation — Practice Tasks¶

All tasks must be solved in Go, Java, and Python. Each task ships with a problem statement, constraints, hints, and a reference solution in all three languages. Validate against the evaluation criteria.

Beginner Tasks (5)¶

Task 1 — Build an adjacency list from an edge array¶

Problem. Given n vertices labelled 0..n-1 and a list of undirected edges, build the adjacency list and print each vertex's neighbors in insertion order.

Input / Output spec. - Input: n, m, then m lines u v. - Output: n lines, line i is i: followed by the space-separated neighbors of i.

Constraints. - 1 <= n <= 10^5, 0 <= m <= 2*10^5. - Vertices are in [0, n). Self-loops allowed; no parallel edges. - Build time: O(n + m).

Hint. Allocate n empty buckets first. For each edge append v to adj[u] and u to adj[v]. Never allocate an n x n matrix — for n = 10^5 that is 10^10 cells.

Reference — Go.

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var n, m int
    fmt.Fscan(in, &n, &m)
    adj := make([][]int, n)
    for i := 0; i < m; i++ {
        var u, v int
        fmt.Fscan(in, &u, &v)
        adj[u] = append(adj[u], v)
        adj[v] = append(adj[v], u)
    }
    for i := 0; i < n; i++ {
        fmt.Fprintf(out, "%d:", i)
        for _, v := range adj[i] {
            fmt.Fprintf(out, " %d", v)
        }
        fmt.Fprintln(out)
    }
}

Reference — Java.

import java.util.*;
import java.io.*;

public class Task1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer tok = new StreamTokenizer(br);
        tok.nextToken(); int n = (int) tok.nval;
        tok.nextToken(); int m = (int) tok.nval;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < m; i++) {
            tok.nextToken(); int u = (int) tok.nval;
            tok.nextToken(); int v = (int) tok.nval;
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(i).append(':');
            for (int v : adj.get(i)) sb.append(' ').append(v);
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

Reference — Python.

import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    adj = [[] for _ in range(n)]
    for _ in range(m):
        u = int(data[idx]); v = int(data[idx + 1]); idx += 2
        adj[u].append(v)
        adj[v].append(u)
    out = []
    for i in range(n):
        out.append(f"{i}:" + "".join(f" {v}" for v in adj[i]))
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    main()

Evaluation criteria. - Build runs in O(n + m). - Each undirected edge appears in both endpoints' lists. - Isolated vertices print an empty neighbor list, not an error.

Task 2 — Build an adjacency matrix and answer edge queries¶

Problem. Given a small directed graph, build a V x V 0/1 adjacency matrix and answer a batch of hasEdge(u, v) queries in O(1) each.

Input / Output spec. - Input: n, m, then m lines u v (directed edge u -> v), then q, then q lines u v. - Output: q lines, true or false.

Constraints. - 1 <= n <= 1000 (so n^2 <= 10^6 cells). - 0 <= m, q <= 10^5. - Each query is O(1).

Hint. A matrix is the right call only because n <= 1000. For directed graphs set M[u][v] only — do not set the symmetric cell.

Reference — Go.

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var n, m int
    fmt.Fscan(in, &n, &m)
    mat := make([][]bool, n)
    for i := range mat {
        mat[i] = make([]bool, n)
    }
    for i := 0; i < m; i++ {
        var u, v int
        fmt.Fscan(in, &u, &v)
        mat[u][v] = true
    }
    var q int
    fmt.Fscan(in, &q)
    for i := 0; i < q; i++ {
        var u, v int
        fmt.Fscan(in, &u, &v)
        fmt.Fprintln(out, mat[u][v])
    }
}

Reference — Java.

import java.util.*;
import java.io.*;

public class Task2 {
    public static void main(String[] args) throws IOException {
        StreamTokenizer tok = new StreamTokenizer(
            new BufferedReader(new InputStreamReader(System.in)));
        tok.nextToken(); int n = (int) tok.nval;
        tok.nextToken(); int m = (int) tok.nval;
        boolean[][] mat = new boolean[n][n];
        for (int i = 0; i < m; i++) {
            tok.nextToken(); int u = (int) tok.nval;
            tok.nextToken(); int v = (int) tok.nval;
            mat[u][v] = true;
        }
        tok.nextToken(); int q = (int) tok.nval;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            tok.nextToken(); int u = (int) tok.nval;
            tok.nextToken(); int v = (int) tok.nval;
            sb.append(mat[u][v]).append('\n');
        }
        System.out.print(sb);
    }
}

Reference — Python.

import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    p = 0
    n = int(data[p]); p += 1
    m = int(data[p]); p += 1
    mat = [bytearray(n) for _ in range(n)]
    for _ in range(m):
        u = int(data[p]); v = int(data[p + 1]); p += 2
        mat[u][v] = 1
    q = int(data[p]); p += 1
    out = []
    for _ in range(q):
        u = int(data[p]); v = int(data[p + 1]); p += 2
        out.append("true" if mat[u][v] else "false")
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    main()

Evaluation criteria. - Each query is O(1). - Directed edges are not made symmetric. - A query hasEdge(u, u) returns true only if a self-loop was inserted.

Task 3 — Convert an edge list to an edge-count summary¶

Problem. Given an undirected edge list, report the degree of every vertex and the total edge count. This forces you to handle the handshake identity (sum of degrees = 2 * edges).

Input / Output spec. - Input: n, m, then m lines u v. - Output: line 1 is m (the edge count); line 2 is n space-separated degrees.

Constraints. - 1 <= n <= 10^6, 0 <= m <= 2*10^6. - O(n + m) time, O(n) extra memory. - Self-loops count 2 toward the degree of their vertex.

Hint. A single degree array. For each edge (u, v) increment deg[u] and deg[v]; a self-loop (v, v) naturally adds 2 to deg[v].

Reference — Go.

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var n, m int
    fmt.Fscan(in, &n, &m)
    deg := make([]int, n)
    for i := 0; i < m; i++ {
        var u, v int
        fmt.Fscan(in, &u, &v)
        deg[u]++
        deg[v]++
    }
    fmt.Fprintln(out, m)
    for i := 0; i < n; i++ {
        if i > 0 {
            out.WriteByte(' ')
        }
        fmt.Fprint(out, deg[i])
    }
    fmt.Fprintln(out)
}

Reference — Java.

import java.util.*;
import java.io.*;

public class Task3 {
    public static void main(String[] args) throws IOException {
        StreamTokenizer tok = new StreamTokenizer(
            new BufferedReader(new InputStreamReader(System.in)));
        tok.nextToken(); int n = (int) tok.nval;
        tok.nextToken(); int m = (int) tok.nval;
        int[] deg = new int[n];
        for (int i = 0; i < m; i++) {
            tok.nextToken(); int u = (int) tok.nval;
            tok.nextToken(); int v = (int) tok.nval;
            deg[u]++;
            deg[v]++;
        }
        StringBuilder sb = new StringBuilder();
        sb.append(m).append('\n');
        for (int i = 0; i < n; i++) {
            if (i > 0) sb.append(' ');
            sb.append(deg[i]);
        }
        System.out.println(sb);
    }
}

Reference — Python.

import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    p = 0
    n = int(data[p]); p += 1
    m = int(data[p]); p += 1
    deg = [0] * n
    for _ in range(m):
        u = int(data[p]); v = int(data[p + 1]); p += 2
        deg[u] += 1
        deg[v] += 1
    sys.stdout.write(str(m) + "\n")
    sys.stdout.write(" ".join(map(str, deg)) + "\n")


if __name__ == "__main__":
    main()

Evaluation criteria. - Sum of degrees equals 2 * m (handshake identity). - Self-loops contribute 2 to the relevant degree. - Single pass, O(n) memory.

Task 4 — Detect a missing reverse edge (undirected validity check)¶

Problem. Given an adjacency list that claims to be undirected, verify it: for every edge u -> v there must be a matching v -> u. Report whether the list is a valid undirected graph.

Input / Output spec. - Input: n, then n lines; line i starts with k_i (the neighbor count) followed by k_i neighbor ids. - Output: true if every directed entry has its reverse, else false.

Constraints. - 1 <= n <= 10^5, total entries <= 4*10^5. - No parallel edges (each (u, v) appears at most once in adj[u]). - O(n + total entries) time.

Hint. Put every (u, v) with u < v into a set, and every (u, v) with u > v reversed to (v, u) into a count. An edge is valid iff both directions are present. Self-loops (v, v) must appear an even number of times overall, but with no parallel edges a self-loop appears once in adj[v] and is its own reverse.

Reference — Go.

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    var n int
    fmt.Fscan(in, &n)
    type pair struct{ a, b int }
    seen := map[pair]bool{}
    adj := make([][]int, n)
    for i := 0; i < n; i++ {
        var k int
        fmt.Fscan(in, &k)
        adj[i] = make([]int, k)
        for j := 0; j < k; j++ {
            fmt.Fscan(in, &adj[i][j])
            seen[pair{i, adj[i][j]}] = true
        }
    }
    valid := true
    for u := 0; u < n && valid; u++ {
        for _, v := range adj[u] {
            if !seen[pair{v, u}] {
                valid = false
                break
            }
        }
    }
    fmt.Println(valid)
}

Reference — Java.

import java.util.*;
import java.io.*;

public class Task4 {
    public static void main(String[] args) throws IOException {
        StreamTokenizer tok = new StreamTokenizer(
            new BufferedReader(new InputStreamReader(System.in)));
        tok.nextToken(); int n = (int) tok.nval;
        Set<Long> seen = new HashSet<>();
        int[][] adj = new int[n][];
        for (int i = 0; i < n; i++) {
            tok.nextToken(); int k = (int) tok.nval;
            adj[i] = new int[k];
            for (int j = 0; j < k; j++) {
                tok.nextToken(); int v = (int) tok.nval;
                adj[i][j] = v;
                seen.add((long) i * 1_000_000_007L + v);
            }
        }
        boolean valid = true;
        outer:
        for (int u = 0; u < n; u++) {
            for (int v : adj[u]) {
                if (!seen.contains((long) v * 1_000_000_007L + u)) {
                    valid = false;
                    break outer;
                }
            }
        }
        System.out.println(valid);
    }
}

Reference — Python.

import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    p = 0
    n = int(data[p]); p += 1
    adj = []
    seen = set()
    for i in range(n):
        k = int(data[p]); p += 1
        row = []
        for _ in range(k):
            v = int(data[p]); p += 1
            row.append(v)
            seen.add((i, v))
        adj.append(row)
    valid = all((v, u) in seen for u in range(n) for v in adj[u])
    print(str(valid).lower())


if __name__ == "__main__":
    main()

Evaluation criteria. - Correctly flags a one-directional edge as invalid. - Self-loops are treated as their own reverse. - Runs in O(n + total entries).

Task 5 — Build a weighted adjacency list¶

Problem. Given an undirected weighted graph, build an adjacency list of (neighbor, weight) pairs and answer weight(u, v) queries, returning -1 if no such edge exists.

Input / Output spec. - Input: n, m, then m lines u v w, then q, then q lines u v. - Output: q lines, each the weight of edge (u, v) or -1.

Constraints. - 1 <= n <= 10^5, 0 <= m, q <= 2*10^5. - 1 <= w <= 10^9. No parallel edges. - Each query is O(degree(u)).

Hint. Store (neighbor, weight) pairs. For a query scan adj[u] for v. Note that 0 is not used as the sentinel here because weights are positive; we return -1 for "no edge".

Reference — Go.

package main

import (
    "bufio"
    "fmt"
    "os"
)

type wEdge struct {
    to int
    w  int64
}

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var n, m int
    fmt.Fscan(in, &n, &m)
    adj := make([][]wEdge, n)
    for i := 0; i < m; i++ {
        var u, v int
        var w int64
        fmt.Fscan(in, &u, &v, &w)
        adj[u] = append(adj[u], wEdge{v, w})
        adj[v] = append(adj[v], wEdge{u, w})
    }
    var q int
    fmt.Fscan(in, &q)
    for i := 0; i < q; i++ {
        var u, v int
        fmt.Fscan(in, &u, &v)
        var ans int64 = -1
        for _, e := range adj[u] {
            if e.to == v {
                ans = e.w
                break
            }
        }
        fmt.Fprintln(out, ans)
    }
}

Reference — Java.

import java.util.*;
import java.io.*;

public class Task5 {
    public static void main(String[] args) throws IOException {
        StreamTokenizer tok = new StreamTokenizer(
            new BufferedReader(new InputStreamReader(System.in)));
        tok.nextToken(); int n = (int) tok.nval;
        tok.nextToken(); int m = (int) tok.nval;
        List<long[]>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            tok.nextToken(); int u = (int) tok.nval;
            tok.nextToken(); int v = (int) tok.nval;
            tok.nextToken(); long w = (long) tok.nval;
            adj[u].add(new long[]{v, w});
            adj[v].add(new long[]{u, w});
        }
        tok.nextToken(); int q = (int) tok.nval;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            tok.nextToken(); int u = (int) tok.nval;
            tok.nextToken(); int v = (int) tok.nval;
            long ans = -1;
            for (long[] e : adj[u]) {
                if (e[0] == v) { ans = e[1]; break; }
            }
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
}

Reference — Python.

import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    p = 0
    n = int(data[p]); p += 1
    m = int(data[p]); p += 1
    adj = [[] for _ in range(n)]
    for _ in range(m):
        u = int(data[p]); v = int(data[p + 1]); w = int(data[p + 2]); p += 3
        adj[u].append((v, w))
        adj[v].append((u, w))
    q = int(data[p]); p += 1
    out = []
    for _ in range(q):
        u = int(data[p]); v = int(data[p + 1]); p += 2
        ans = -1
        for to, w in adj[u]:
            if to == v:
                ans = w
                break
        out.append(str(ans))
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    main()

Evaluation criteria. - Returns -1 for a non-existent edge, never 0. - Stores each undirected edge in both endpoints' lists with the same weight. - Each query is O(degree(u)).

Intermediate Tasks (5)¶

Task 6 — Build CSR from an edge list and answer neighbor queries¶

Problem. Build a Compressed Sparse Row (CSR) representation of a directed graph using the two-pass counting algorithm, then answer neighbors(u) queries by returning the slice target[offset[u]:offset[u+1]].

Input / Output spec. - Input: n, m, then m lines u v (directed), then q, then q query vertices. - Output: q lines; each line is the space-separated out-neighbors of the queried vertex (in edge-input order), or empty.

Constraints. - 1 <= n <= 10^6, 0 <= m <= 5*10^6, 0 <= q <= 10^5. - Build: O(n + m). Each query: O(degree(u)).

Hint. Three steps: count out-degrees into offset[u+1]; prefix-sum offset; then place each target using a separate cursor copy so you never corrupt offset.

Reference — Go.

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var n, m int
    fmt.Fscan(in, &n, &m)
    us := make([]int, m)
    vs := make([]int, m)
    offset := make([]int, n+1)
    for i := 0; i < m; i++ {
        fmt.Fscan(in, &us[i], &vs[i])
        offset[us[i]+1]++
    }
    for i := 1; i <= n; i++ {
        offset[i] += offset[i-1]
    }
    target := make([]int, m)
    cursor := make([]int, n)
    copy(cursor, offset[:n])
    for i := 0; i < m; i++ {
        u := us[i]
        target[cursor[u]] = vs[i]
        cursor[u]++
    }
    var q int
    fmt.Fscan(in, &q)
    for i := 0; i < q; i++ {
        var u int
        fmt.Fscan(in, &u)
        first := true
        for k := offset[u]; k < offset[u+1]; k++ {
            if !first {
                out.WriteByte(' ')
            }
            fmt.Fprint(out, target[k])
            first = false
        }
        fmt.Fprintln(out)
    }
}

Reference — Java.

import java.util.*;
import java.io.*;

public class Task6 {
    public static void main(String[] args) throws IOException {
        StreamTokenizer tok = new StreamTokenizer(
            new BufferedReader(new InputStreamReader(System.in)));
        tok.nextToken(); int n = (int) tok.nval;
        tok.nextToken(); int m = (int) tok.nval;
        int[] us = new int[m], vs = new int[m];
        int[] offset = new int[n + 1];
        for (int i = 0; i < m; i++) {
            tok.nextToken(); us[i] = (int) tok.nval;
            tok.nextToken(); vs[i] = (int) tok.nval;
            offset[us[i] + 1]++;
        }
        for (int i = 1; i <= n; i++) offset[i] += offset[i - 1];
        int[] target = new int[m];
        int[] cursor = Arrays.copyOf(offset, n);
        for (int i = 0; i < m; i++) target[cursor[us[i]]++] = vs[i];

        tok.nextToken(); int q = (int) tok.nval;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            tok.nextToken(); int u = (int) tok.nval;
            for (int k = offset[u]; k < offset[u + 1]; k++) {
                if (k > offset[u]) sb.append(' ');
                sb.append(target[k]);
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

Reference — Python.

import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    p = 0
    n = int(data[p]); p += 1
    m = int(data[p]); p += 1
    us = [0] * m
    vs = [0] * m
    offset = [0] * (n + 1)
    for i in range(m):
        u = int(data[p]); v = int(data[p + 1]); p += 2
        us[i] = u
        vs[i] = v
        offset[u + 1] += 1
    for i in range(1, n + 1):
        offset[i] += offset[i - 1]
    target = [0] * m
    cursor = offset[:n]
    for i in range(m):
        u = us[i]
        target[cursor[u]] = vs[i]
        cursor[u] += 1
    q = int(data[p]); p += 1
    out = []
    for _ in range(q):
        u = int(data[p]); p += 1
        out.append(" ".join(map(str, target[offset[u]:offset[u + 1]])))
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    main()

Evaluation criteria. - offset[u+1] - offset[u] equals the out-degree of u. - cursor is a separate copy; offset is never mutated during placement. - Build is O(n + m); each query is O(degree).

Task 7 — Convert an adjacency list to a deduplicated edge list¶

Problem. Given an undirected adjacency list, output the edge list with each undirected edge listed exactly once. Filter using the u < v convention so (a, b) and (b, a) collapse to one entry. Sort the output for determinism.

Input / Output spec. - Input: n, then n lines; line i is k_i followed by k_i neighbors. - Output: line 1 is the edge count e; then e lines u v with u <= v, sorted ascending.

Constraints. - 1 <= n <= 10^5, total entries <= 4*10^5. - Self-loops (v, v) are emitted once. - O(n + total entries + e log e) time.

Hint. For every stored (u, v), emit it only if u <= v. This relies on the list being a valid undirected graph (each edge stored at both endpoints), so the u < v half is exactly one copy; self-loops have u == v.

Reference — Go.

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var n int
    fmt.Fscan(in, &n)
    type edge struct{ u, v int }
    var edges []edge
    for u := 0; u < n; u++ {
        var k int
        fmt.Fscan(in, &k)
        for j := 0; j < k; j++ {
            var v int
            fmt.Fscan(in, &v)
            if u <= v {
                edges = append(edges, edge{u, v})
            }
        }
    }
    sort.Slice(edges, func(i, j int) bool {
        if edges[i].u != edges[j].u {
            return edges[i].u < edges[j].u
        }
        return edges[i].v < edges[j].v
    })
    fmt.Fprintln(out, len(edges))
    for _, e := range edges {
        fmt.Fprintln(out, e.u, e.v)
    }
}

Reference — Java.

import java.util.*;
import java.io.*;

public class Task7 {
    public static void main(String[] args) throws IOException {
        StreamTokenizer tok = new StreamTokenizer(
            new BufferedReader(new InputStreamReader(System.in)));
        tok.nextToken(); int n = (int) tok.nval;
        List<int[]> edges = new ArrayList<>();
        for (int u = 0; u < n; u++) {
            tok.nextToken(); int k = (int) tok.nval;
            for (int j = 0; j < k; j++) {
                tok.nextToken(); int v = (int) tok.nval;
                if (u <= v) edges.add(new int[]{u, v});
            }
        }
        edges.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        StringBuilder sb = new StringBuilder();
        sb.append(edges.size()).append('\n');
        for (int[] e : edges) sb.append(e[0]).append(' ').append(e[1]).append('\n');
        System.out.print(sb);
    }
}

Reference — Python.

import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    p = 0
    n = int(data[p]); p += 1
    edges = []
    for u in range(n):
        k = int(data[p]); p += 1
        for _ in range(k):
            v = int(data[p]); p += 1
            if u <= v:
                edges.append((u, v))
    edges.sort()
    out = [str(len(edges))]
    out.extend(f"{u} {v}" for u, v in edges)
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    main()

Evaluation criteria. - Each undirected edge appears exactly once in the output. - Self-loops appear exactly once. - Output is sorted; edge count matches len(edges).

Task 8 — Implicit grid graph: count connected components¶

Problem. Given a grid of . (open) and # (wall), count the connected components of open cells, treating each open cell as a vertex connected to its orthogonal open neighbors. Do not build an explicit graph — compute neighbors on the fly.

Input / Output spec. - Input: rows, cols, then rows lines of the grid. - Output: the number of connected components of open cells.

Constraints. - 1 <= rows, cols <= 1000. - 4-directional connectivity. - O(rows * cols) time and memory.

Hint. The grid is the graph. Run BFS/DFS from each unvisited open cell, using the four offset deltas and bounds checks; each BFS marks one component.

Reference — Go.

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    var rows, cols int
    fmt.Fscan(in, &rows, &cols)
    grid := make([]string, rows)
    for i := range grid {
        fmt.Fscan(in, &grid[i])
    }
    seen := make([][]bool, rows)
    for i := range seen {
        seen[i] = make([]bool, cols)
    }
    deltas := [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    count := 0
    queue := make([][2]int, 0, rows*cols)
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] != '.' || seen[r][c] {
                continue
            }
            count++
            queue = queue[:0]
            queue = append(queue, [2]int{r, c})
            seen[r][c] = true
            for len(queue) > 0 {
                cell := queue[0]
                queue = queue[1:]
                for _, d := range deltas {
                    nr, nc := cell[0]+d[0], cell[1]+d[1]
                    if nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
                        grid[nr][nc] == '.' && !seen[nr][nc] {
                        seen[nr][nc] = true
                        queue = append(queue, [2]int{nr, nc})
                    }
                }
            }
        }
    }
    fmt.Println(count)
}