結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
in1.txt AC 34 ms
9628 KB
in2.txt AC 32 ms
9628 KB
in3.txt AC 41 ms
9624 KB
in4.txt AC 31 ms
9640 KB
in5.txt AC 31 ms
9664 KB
in6.txt AC 32 ms
9708 KB
in7.txt AC 35 ms
10104 KB
in8.txt AC 45 ms
11504 KB
in9.txt AC 100 ms
15420 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);
        }

        foreach (int j in Group[rY])
        {
            Group[rX].Add(j);
        }
        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