标签:Circle Detect

REPORT-hihoCoder太阁最新面经算法竞赛15(AC #1 #2 #3) – 16.11.19

REPORT-hihoCoder太阁最新面经算法竞赛15(AC #1 #2 #3) – 16.11.19

#1 Boarding Passes
如果有一个城市A,不在终点城市里或者它作为终点城市的次数比比作为起点城市的次数少一次,那么这个就是总起点城市。
总终点城市同理。
最开始我还以为是拓扑排序,结果只过了20%然后才意识到这个图可能会有环。

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

namespace Boarding_Passes
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = Convert.ToInt32(Console.ReadLine().Trim());
            
            Dictionary<string, int> startcities = new Dictionary<string, int>();
            Dictionary<string, int> endcities = new Dictionary<string, int>();
            int startcitycount = 0, endcitycount = 0;
            for (int i = 0; i < n; ++i)
            {
                string[] inp = Console.ReadLine().Trim().Split();
                if (!startcities.ContainsKey(inp[0]))
                {
                    startcitycount++;
                    startcities.Add(inp[0], 1);
                }
                else
                {
                    startcities[inp[0]]++;
                }
                if (!endcities.ContainsKey(inp[1]))
                {
                    endcitycount++;
                    endcities.Add(inp[1], 1);
                }
                else
                {
                    endcities[inp[1]]++;
                }
            }

            foreach (var temp in startcities)
            {
                if (!endcities.ContainsKey(temp.Key) || endcities[temp.Key] + 1 == startcities[temp.Key])
                {
                    Console.Write(temp.Key);
                    break;
                }
            }
            Console.Write(" ");
            foreach (var temp in endcities)
            {
                if (!startcities.ContainsKey(temp.Key) || startcities[temp.Key] + 1 == endcities[temp.Key])
                {
                    Console.Write(temp.Key);
                    break;
                }
            }
        }
    }
}

#2 Sorting Photo Files
排序。

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

namespace Sorting_Photo_Files
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> partStr = new List<string>();
            Dictionary<string, List<int>> partInt = new Dictionary<string, List<int>>();
            int N = Convert.ToInt32(Console.ReadLine().Trim());
            for (int i = 0; i < N; i++)
            {
                string filename = Console.ReadLine().Trim();
                var sp = split(filename);
                if (!partInt.ContainsKey(sp.Key))
                {
                    List<int> l = new List<int>();
                    partStr.Add(sp.Key);
                    l.Add(sp.Value);
                    partInt.Add(sp.Key, l);
                }
                else
                {
                    partInt[sp.Key].Add(sp.Value);
                }
            }
            foreach(var temp in partInt)
            {
                temp.Value.Sort();
            }
            partStr.Sort();
            foreach(var temp in partStr)
            {
                foreach (var temp2 in partInt[temp])
                {
                    Console.WriteLine("{0}{1}", temp, temp2);
                }
            }
        }
        public static KeyValuePair<string, int> split(string str)
        {
            KeyValuePair<string, int> retdata = new KeyValuePair<string, int>();
            for (int i = 0; i < str.Length; i++)
            {
                if (str[i] >= '0' && str[i] <= '9')
                {
                    string partA = str.Substring(0, i);
                    string partB = str.Substring(i);
                    retdata = new KeyValuePair<string, int>(partA, Convert.ToInt32(partB));
                    break;
                }
            }
            return retdata;
        }
    }
}

#3 Circle Detect
判环。DFS。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Circle_Detect
{
class Program
{
static void Main(string[] args)
{
int T = Convert.ToInt32(Console.ReadLine().Trim());
for (int Times = 0; Times < T; Times++) { string[] inp = Console.ReadLine().Trim().Split(' '); int n = Convert.ToInt32(inp[0]); int m = Convert.ToInt32(inp[1]); List[] g = new List[n + 5];
for (int i = 0; i < n + 5; i++) { g[i] = new List();
}
bool[] visited = new bool[n + 5];
for (int i = 0; i < n + 5; i++) visited[i] = false; for (int i = 0; i < m; i++) { inp = Console.ReadLine().Trim().Split(' '); int a = Convert.ToInt32(inp[0]) - 1; int b = Convert.ToInt32(inp[1]) - 1; if (!g[a].Contains(b)) g[a].Add(b); } bool flag = false; for (int i = 0; i < n; i++) { if (dfs(visited, i, g)) { flag = true; break; } } if (flag) Console.WriteLine("YES"); else Console.WriteLine("NO"); } } static bool dfs(bool[] vis,int p,List[] g)
{
if (vis[p]) return true;
vis[p] = true;
for (int i = 0; i < g[p].Count(); i++) { if (dfs(vis, g[p][i], g)) return true; } vis[p] = false; return false; } } }