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 |