Submission #311886


Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


class B2
{
    bool[] visited;
    List<int>[] children;
    int Solve()
    {
        string[] str = Console.ReadLine().Split(' ');
        int n = int.Parse(str[0]);
        int m = int.Parse(str[1]);

        children = new List<int>[n];
        for (int i = 0; i < n; i++)
            children[i] = new List<int>();

        for (int i = 0; i < m; i++)
        {
            string[] s = Console.ReadLine().Split(' ');
            int x = int.Parse(s[0]) - 1;
            int y = int.Parse(s[1]) - 1;
            children[x].Add(y);
            children[y].Add(x);
        }

        visited = new bool[n];
        int need = 0;
        for(int i = 0; i < n ; i++)
        {
            if (!visited[i])
            {
                dfs(i);
                need++;
            }
        }
        return need - 1;
    }

    void dfs(int node)
    {
        visited[node] = true;
        foreach (int index in children[node])
            if (!visited[index]) dfs(index);
    }

    static void Main(string[] args)
    {
        Console.WriteLine(new B2().Solve());
    }
}

Submission Info

Submission Time
Task B - 道路工事
User paralleltree
Language C# (Mono 2.10.8.1)
Score 100
Code Size 1220 Byte
Status AC
Exec Time 327 ms
Memory 23308 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 20
Set Name Test Cases
Sample sample1.txt, sample2.txt
All 0.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt
Case Name Status Exec Time Memory
0.txt AC 117 ms 7716 KB
1.txt AC 112 ms 7844 KB
10.txt AC 113 ms 7840 KB
11.txt AC 112 ms 7836 KB
12.txt AC 110 ms 7760 KB
13.txt AC 112 ms 7836 KB
14.txt AC 115 ms 7840 KB
15.txt AC 222 ms 10276 KB
16.txt AC 136 ms 11932 KB
17.txt AC 135 ms 11940 KB
18.txt AC 137 ms 11932 KB
19.txt AC 327 ms 23308 KB
2.txt AC 112 ms 7840 KB
3.txt AC 111 ms 7832 KB
4.txt AC 114 ms 7844 KB
5.txt AC 118 ms 7832 KB
6.txt AC 114 ms 7836 KB
7.txt AC 114 ms 7840 KB
8.txt AC 117 ms 7848 KB
9.txt AC 115 ms 7836 KB
sample1.txt AC 112 ms 7828 KB
sample2.txt AC 112 ms 7836 KB