提出 #459368

---

ソースコード 拡げる

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

public class ClassName
{
    public static void Main()
    {
        new ClassName().Entry();
    }//Main


    bool[] used;
    HashSet<int>[] edges;
    UnionFind uf;
    int[] parent;
    void Entry()
    {
        var tmp = intSplit(' ');
        int V = tmp[0];
        int E = tmp[1];
        edges = new HashSet<int>[V];
        for (int i = 0; i < V; i++)
        {
            edges[i] = new HashSet<int>();
        }//for i
        for (int i = 0; i < E; i++)
        {
            tmp = intSplit(' ');
            int a = tmp[0];
            int b = tmp[1];
            edges[a].Add(b);
            edges[b].Add(a);
        }//for i
        uf = new UnionFind(V);
        used = new bool[V];
        parent = Enumerable.Repeat(-1, V).ToArray();
        DFS(0,-1);


        var hash = new HashSet<int>();
        for (int i = 0; i < V; i++)
        {
            if(uf.IsParent(i)){
                hash.Add(i);
            }
        }//for i
        string res ="";
        if (hash.Count == 1)
        {
            res = "IMPOSSIBLE";
        }
        else if (hash.Count == 2)
        {
            res = "0";
        }
        else
        {
            if (V == 3)
            {
                res = "IMPOSSIBLE";
            }
            else
            {
                res = "1";
            }
        }

        Console.WriteLine(res);
    }

    private void DFS(int cur,int prev)
    {
        used[cur] = true;

        foreach (var next in edges[cur])
        {
            if (next == prev)
            {
                continue;
            }
            if (used[next])
            {
                Fill(next, cur);
                continue;
            }
            parent[next] = cur;
            DFS(next,cur);
        }//foreach item

        used[cur] = false;


    }

    private void Fill(int p, int c)
    {
        if (p == c)
        {
            return;
        }
        uf.Unite(p, c);
        parent[c] = p;
        Fill(p, parent[c]);
    }

    /// <summary>
    /// varified by SRM472 DIV1 Medium TwoSidedCards
    /// 0 : サイズを指定して初期化
    /// -1 で初期化。
    /// 初期化に O(len)
    /// 関数は平均 A^-1 (len)
    /// </summary>
    public class UnionFind
    {
       public int[] parent;    //UnionFind の本体

        /// <summary>
        /// -1 で初期化
        /// O( n )
        /// </summary>
        /// <param name="len">要素の数</param>
        public UnionFind(int len)
        {
            parent = new int[len];
            for (int i = 0; i < len; i++)
                parent[i] = -1;
        }//Constractor

        /// <summary>
        /// 2 つの要素を繋げる
        /// O( A(n) )
        /// </summary>
        /// <param name="x">繋げられる要素</param>
        /// <param name="y">繋げる要素</param>
        /// <returns>繋げることができたかどうか</returns>
        public bool Unite(int x, int y)
        {
            x = Find(x);
            y = Find(y);
            if (x == y)
                return false;

            if (parent[y] < parent[x])    //swap
            {
                int tmp = x;
                x = y;
                y = tmp;
            }
            parent[x] += parent[y];
            parent[y] = x;
            return true;
        }//Unite

        /// <summary>
        /// 同値類の要素の親を探す
        /// O( A(n) )
        /// </summary>
        /// <param name="x">親を探す要素</param>
        /// <returns>同じ</returns>
        public int Find(int x)
        {
            if (parent[x] < 0)
                return x;
            return parent[x] = Find(parent[x]);
        }//Find

        /// <summary>
        /// 同値類かどうか
        /// O( A(n) )
        /// </summary>
        /// <param name="x">比べられる要素</param>
        /// <param name="y">比べる要素</param>
        /// <returns>true : 同値類</returns>
        public bool Same(int x, int y)
        {
            return Find(x) == Find(y);
        }//Same

        /// <summary>
        /// 同値類の数を数える
        /// O( A(n) )
        /// </summary>
        /// <param name="x">同値類を数える要素</param>
        /// <returns>同値類の数</returns>
        public int Size(int x)
        {
            return -parent[Find(x)];
        }//Size

        /// <summary>
        /// UnionFind の親（根）になっているかの判定
        /// O( 1 )
        /// </summary>
        /// <param name="x">判定するインデックス</param>
        /// <returns>true : 親</returns>
        public bool IsParent(int x)
        {
            return parent[x] < 0;
        }//IsPaarent

    }//UnonFind

    string strRead()
    {
        return Console.ReadLine();
    }

    int intRead()
    {
        return int.Parse(Console.ReadLine());
    }

    long longRead()
    {
        return long.Parse(Console.ReadLine());
    }

    double doubleRead()
    {
        return double.Parse(Console.ReadLine());
    }

    string[] strSplit(char c)
    {
        return Console.ReadLine().Split(new char[] { c }, StringSplitOptions.RemoveEmptyEntries);
    }

    int[] intSplit(char c)
    {
        return Array.ConvertAll<string, int>(Console.ReadLine().Split(new char[] { c }, StringSplitOptions.RemoveEmptyEntries), int.Parse);
    }

    long[] longSplit(char r)
    {
        return Array.ConvertAll<string, long>(Console.ReadLine().Split(new char[] { r }, StringSplitOptions.RemoveEmptyEntries), long.Parse);
    }

    double[] doubleSplit(char c)
    {
        return Array.ConvertAll<string, double>(Console.ReadLine().Split(new char[] { c }, StringSplitOptions.RemoveEmptyEntries), double.Parse);
    }

}//ClassName

提出情報

ジャッジ結果