4764 2023. 03. 31 11:28:20 TortelliniJr Parti (75 pont) csharp Hibás válasz 3/75 111ms 44616 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 Összpont Teszt Verdikt Idő Memória
base 3/75
1 Hibás válasz 0/0 32ms 20204 KiB
2 Futási hiba 0/0 111ms 44616 KiB
3 Hibás válasz 0/3 29ms 20952 KiB
4 Hibás válasz 0/3 30ms 21724 KiB
5 Elfogadva 3/3 30ms 21748 KiB
6 Hibás válasz 0/3 30ms 22724 KiB
7 Hibás válasz 0/3 30ms 22784 KiB
8 Hibás válasz 0/4 32ms 23332 KiB
9 Hibás válasz 0/4 32ms 24068 KiB
10 Hibás válasz 0/4 35ms 24952 KiB
11 Hibás válasz 0/4 32ms 24992 KiB
12 Hibás válasz 0/4 35ms 26040 KiB
13 Hibás válasz 0/4 37ms 27252 KiB
14 Hibás válasz 0/4 39ms 28612 KiB
15 Futási hiba 0/4 41ms 41476 KiB
16 Futási hiba 0/4 39ms 41424 KiB
17 Futási hiba 0/4 39ms 41288 KiB
18 Futási hiba 0/4 39ms 41248 KiB
19 Futási hiba 0/4 39ms 41156 KiB
20 Futási hiba 0/4 39ms 41220 KiB
21 Futási hiba 0/4 39ms 40724 KiB
22 Hibás válasz 0/4 30ms 24788 KiB