47662023-03-31 11:29:53TortelliniJrParti (75 pont)csharpHibás válasz 3/75111ms44408 KiB
using System;
using System.Collections.Generic;
using System.Linq;

class MainClass
{
    static int n, ksz;
    static List<int>[] g;
    static List<int>[] g2;
    static bool[] volt;
    static bool[] volt2;
    static List<int> top;
    static int[] scc;

    static void dfs(int x)
    {
        if (volt[x]) return;
        volt[x] = true;
        foreach (int i in g[x]) dfs(i);
        top.Add(x);
    }

    static void dfs2(int y)
    {
        if (volt2[y]) return;
        volt2[y] = true;
        foreach (int i in g2[y]) dfs2(i);
        scc[y] = ksz;
    }

    public static void Main(string[] args)
    {
        n = int.Parse(Console.ReadLine());
        g = new List<int>[n + 1];
        g2 = new List<int>[n + 1];
        for (int i = 1; i <= n; ++i)
        {
            g[i] = new List<int>();
            g2[i] = new List<int>();
        }
        volt = new bool[n + 1];
        volt2 = new bool[n + 1];
        top = new List<int>();
        scc = new int[n + 1];
        for (int i = 1; i <= n; ++i)
        {
            string[] input = Console.ReadLine().Split();
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            g[i].Add(a);
            g[i].Add(b);
            g2[a].Add(i);
            g2[b].Add(i);
        }
        for (int i = 1; i <= n; ++i) dfs(i);
        top.Reverse();
        foreach (int cs in top)
        {
            if (!volt2[cs])
            {
                ++ksz;
                dfs2(cs);
            }
        }
        bool[] joscc = new bool[ksz + 1];
        for (int i = 1; i <= n; ++i)
        {
            int db = 0;
            foreach (int j in g2[i])
            {
                if (scc[j] == scc[i])
                {
                    ++db;
                }
            }
            if (db != 2)
            {
                joscc[scc[i]] = false;
            }
        }
        int[] cnt = new int[ksz + 1];
        for (int i = 1; i <= n; ++i)
        {
            ++cnt[scc[i]];
        }
        int maxscc = 0, maxcnt = 0;
        for (int i = 1; i <= ksz; ++i)
        {
            if ((maxscc == 0 || maxcnt < cnt[i]) && joscc[i])
            {
                maxscc = i;
                maxcnt = cnt[i];
            }
        }
        Console.WriteLine(maxcnt);
        for (int i = 1; i <= n; ++i)
        {
            if (scc[i] == maxscc)
            {
                Console.Write(i + " ");
            }
        }
        Console.WriteLine();
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base3/75
1Hibás válasz0/029ms20632 KiB
2Futási hiba0/0111ms44408 KiB
3Hibás válasz0/329ms21592 KiB
4Hibás válasz0/330ms21988 KiB
5Elfogadva3/329ms22220 KiB
6Hibás válasz0/329ms22500 KiB
7Hibás válasz0/330ms23248 KiB
8Hibás válasz0/432ms23492 KiB
9Hibás válasz0/432ms24120 KiB
10Hibás válasz0/435ms25584 KiB
11Hibás válasz0/432ms24532 KiB
12Hibás válasz0/434ms25456 KiB
13Hibás válasz0/437ms27356 KiB
14Hibás válasz0/439ms28344 KiB
15Futási hiba0/441ms41804 KiB
16Futási hiba0/443ms41688 KiB
17Futási hiba0/441ms41640 KiB
18Futási hiba0/439ms41596 KiB
19Futási hiba0/439ms41552 KiB
20Futási hiba0/441ms41252 KiB
21Futási hiba0/441ms41028 KiB
22Hibás válasz0/430ms24416 KiB