4766 | 2023. 03. 31 11:29:53 | TortelliniJr | Parti (75 pont) | csharp | Hibás válasz 3/75 | 111ms | 44408 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 | 29ms | 20632 KiB | |||
2 | Futási hiba | 0/0 | 111ms | 44408 KiB | |||
3 | Hibás válasz | 0/3 | 29ms | 21592 KiB | |||
4 | Hibás válasz | 0/3 | 30ms | 21988 KiB | |||
5 | Elfogadva | 3/3 | 29ms | 22220 KiB | |||
6 | Hibás válasz | 0/3 | 29ms | 22500 KiB | |||
7 | Hibás válasz | 0/3 | 30ms | 23248 KiB | |||
8 | Hibás válasz | 0/4 | 32ms | 23492 KiB | |||
9 | Hibás válasz | 0/4 | 32ms | 24120 KiB | |||
10 | Hibás válasz | 0/4 | 35ms | 25584 KiB | |||
11 | Hibás válasz | 0/4 | 32ms | 24532 KiB | |||
12 | Hibás válasz | 0/4 | 34ms | 25456 KiB | |||
13 | Hibás válasz | 0/4 | 37ms | 27356 KiB | |||
14 | Hibás válasz | 0/4 | 39ms | 28344 KiB | |||
15 | Futási hiba | 0/4 | 41ms | 41804 KiB | |||
16 | Futási hiba | 0/4 | 43ms | 41688 KiB | |||
17 | Futási hiba | 0/4 | 41ms | 41640 KiB | |||
18 | Futási hiba | 0/4 | 39ms | 41596 KiB | |||
19 | Futási hiba | 0/4 | 39ms | 41552 KiB | |||
20 | Futási hiba | 0/4 | 41ms | 41252 KiB | |||
21 | Futási hiba | 0/4 | 41ms | 41028 KiB | |||
22 | Hibás válasz | 0/4 | 30ms | 24416 KiB |