結果

問題 No.416 旅行会社
ユーザー mban
提出日時 2017-03-21 02:39:33
言語 C#
(mono 4.8.0)
結果
TLE  
実行時間 -
コード長 4372 Byte
コンパイル時間 316 ms
使用メモリ 15416 KB

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
in1.txt AC 31 ms
9628 KB
in2.txt AC 31 ms
9636 KB
in3.txt AC 31 ms
9640 KB
in4.txt AC 31 ms
9656 KB
in5.txt AC 34 ms
9688 KB
in6.txt AC 44 ms
9728 KB
in7.txt AC 34 ms
10136 KB
in8.txt AC 46 ms
11588 KB
in9.txt AC 99 ms
15416 KB
line1.txt TLE -
line2.txt -- -
line11.txt -- -
line21.txt -- -
line31.txt -- -
line32.txt -- -
line33.txt -- -
line34.txt -- -
line35.txt -- -
line41.txt -- -
line42.txt -- -
テストケース一括ダウンロード

ソースコード

diff #
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.IO;
using System.ComponentModel;

class Program
{
    static void Main(string[] args)
    {
        var alice = new Magatro();
        alice.Scan();
        alice.Solve();
    }
}

public class Scanner
{
    private StreamReader Sr;
    private string[] S;
    private int Index;
    private const char Separator = ' ';

    public Scanner() : this(Console.OpenStandardInput())
    {
        Index = 0;
        S = new string[0];
    }
    public Scanner(Stream source)
    {
        Sr = new StreamReader(source);
    }

    private string[] Line()
    {
        return Sr.ReadLine().Split(Separator);
    }

    public string Next()
    {
        string result;
        if (Index >= S.Length)
        {
            S = Line();
            Index = 0;
        }
        result = S[Index];
        Index++;
        return result;
    }
    public T Next<T>()
    {
        var converter = TypeDescriptor.GetConverter(typeof(T));
        return (T)converter.ConvertFromString(Next());

    }
    public int NextInt()
    {
        return int.Parse(Next());
    }
    public double NextDouble()
    {
        return double.Parse(Next());
    }
    public long NextLong()
    {
        return long.Parse(Next());
    }
    public decimal NextDecimal()
    {
        return decimal.Parse(Next());
    }
    public string[] StringArray(int index = 0)
    {
        Next();
        Index = S.Length;
        return S.Skip(index).ToArray();
    }
    public int[] IntArray(int index = 0)
    {
        return StringArray(index).Select(int.Parse).ToArray();
    }
    public long[] LongArray(int index = 0)
    {
        return StringArray(index).Select(long.Parse).ToArray();
    }
    public bool EndOfStream
    {
        get { return Sr.EndOfStream; }
    }
}

public class Magatro
{
    private int N, M, Q;
    private Bridge[] AB, CD;
    private int[] Anser;
    private int[] Par;
    private List<int>[] Group;

    public void Scan()
    {
        Scanner cin = new Scanner();
        N = cin.NextInt();
        M = cin.NextInt();
        Q = cin.NextInt();
        var h = new HashSet<Bridge>();
        CD = new Bridge[Q];
        AB = new Bridge[M];
        for (int i = 0; i < M; i++)
        {
            AB[i] = new Bridge(cin.NextInt() - 1, cin.NextInt() - 1);
        }
        for (int i = 0; i < Q; i++)
        {
            CD[i] = new Bridge(cin.NextInt() - 1, cin.NextInt() - 1);
        }
    }

    private bool Same(int x, int y)
    {
        return Root(x) == Root(y);
    }

    private void Union(int x, int y, int i)
    {
        int rX = Root(x);
        int rY = Root(y);
        if (rX == rY)
        {
            return;
        }
        int rZero = Root(0);
        if (rZero == rX)
        {
            foreach (int j in Group[rY])
            {
                Anser[j] = i;
            }
        }
        else if (rZero == rY)
        {
            foreach (int j in Group[rX])
            {
                Anser[j] = i;
            }
        }
        if (Group[rX].Count < Group[rY].Count)
        {
            Swap(ref rX, ref rY);
        }

        Group[rX].AddRange(Group[rY]);
        Par[rY] = rX;
    }



    //かっこつけたかった
    private void Swap(ref int a, ref int b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }

    private int Root(int x)
    {
        return Par[x] == x ? x : Root(Par[x]);
    }

    public void Solve()
    {
        AB = AB.Except(CD).ToArray();
        Par = new int[N];
        for (int i = 0; i < N; i++)
        {
            Par[i] = i;
        }
        Group = new List<int>[N];
        for (int i = 0; i < N; i++)
        {
            Group[i] = new List<int>();
            Group[i].Add(i);
        }
        Anser = new int[N];
        foreach (var b in AB)
        {
            Union(b.A, b.B, -1);
        }

        for(int i = Q - 1; i >= 0; i--)
        {
            var b = CD[i];
            Union(b.A, b.B, i + 1);
        }

        for(int i = 1; i < N; i++)
        {
            Console.WriteLine(Anser[i]);
        }
    }

}

struct Bridge
{
    public int A, B;
    public Bridge(int a, int b)
    {
        A = a;
        B = b;
    }
}
0