Rejudge 公告 875 已更新範圍並 rejudge
IOICamp 2024 題目公開！ 連結
程式解題社網站 程式解題社網站上線了！

Submit

Status

Discussion / Solution

Ranklist

Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (4/4)

Tags

ioicamp ioicamp-2021

Description

給定一個 $N$ 點 $M$ 邊的有向圖，請將它拆成若干個有向環或有向鍊，且每個節點都在恰一個部分上。在所有可能的拆法下，請找出一個鍊最少的拆法。

Input Format

輸入第一行有兩個整數 $N$ 與 $M$ ，代表點數與邊數。

接著 $M$ 行，第 $i$ 行有兩個正整數 $u_{i}$ 與 $v_{i}$ ，代表圖中有一條 $u_{i}$ 到 $v_{i}$ 的有向邊。

$1 \leq N \leq 500$
$0 \leq M \leq N \times (N - 1)$
$1 \leq u_{i}, v_{i} \leq N, u_{i} \neq v_{i}$
保證每條有向邊只會出現至多一次

Output Format

請輸出一行，該行有一個數字代表最少需要幾條鍊。

Sample Input 1

Sample Output 1

Sample Input 2

3 2
1 2
2 3

Sample Output 2

Sample Input 3

3 0

Sample Output 3

Hints

Problem Source

IOICamp 2021 Day2 pE

Subtasks

No.	Testdata Range	Constraints	Score
1	0~2	範例測資	0
2	0~129	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	262144	65536	1 2
1	1000	262144	65536	1 2
2	1000	262144	65536	1 2
3	1000	262144	65536	2
4	1000	262144	65536	2
5	1000	262144	65536	2
6	1000	262144	65536	2
7	1000	262144	65536	2
8	1000	262144	65536	2
9	1000	262144	65536	2
10	1000	262144	65536	2
11	1000	262144	65536	2
12	1000	262144	65536	2
13	1000	262144	65536	2
14	1000	262144	65536	2
15	1000	262144	65536	2
16	1000	262144	65536	2
17	1000	262144	65536	2
18	1000	262144	65536	2
19	1000	262144	65536	2
20	1000	262144	65536	2
21	1000	262144	65536	2
22	1000	262144	65536	2
23	1000	262144	65536	2
24	1000	262144	65536	2
25	1000	262144	65536	2
26	1000	262144	65536	2
27	1000	262144	65536	2
28	1000	262144	65536	2
29	1000	262144	65536	2
30	1000	262144	65536	2
31	1000	262144	65536	2
32	1000	262144	65536	2
33	1000	262144	65536	2
34	1000	262144	65536	2
35	1000	262144	65536	2
36	1000	262144	65536	2
37	1000	262144	65536	2
38	1000	262144	65536	2
39	1000	262144	65536	2
40	1000	262144	65536	2
41	1000	262144	65536	2
42	1000	262144	65536	2
43	1000	262144	65536	2
44	1000	262144	65536	2
45	1000	262144	65536	2
46	1000	262144	65536	2
47	1000	262144	65536	2
48	1000	262144	65536	2
49	1000	262144	65536	2
50	1000	262144	65536	2
51	1000	262144	65536	2
52	1000	262144	65536	2
53	1000	262144	65536	2
54	1000	262144	65536	2
55	1000	262144	65536	2
56	1000	262144	65536	2
57	1000	262144	65536	2
58	1000	262144	65536	2
59	1000	262144	65536	2
60	1000	262144	65536	2
61	1000	262144	65536	2
62	1000	262144	65536	2
63	1000	262144	65536	2
64	1000	262144	65536	2
65	1000	262144	65536	2
66	1000	262144	65536	2
67	1000	262144	65536	2
68	1000	262144	65536	2
69	1000	262144	65536	2
70	1000	262144	65536	2
71	1000	262144	65536	2
72	1000	262144	65536	2
73	1000	262144	65536	2
74	1000	262144	65536	2
75	1000	262144	65536	2
76	1000	262144	65536	2
77	1000	262144	65536	2
78	1000	262144	65536	2
79	1000	262144	65536	2
80	1000	262144	65536	2
81	1000	262144	65536	2
82	1000	262144	65536	2
83	1000	262144	65536	2
84	1000	262144	65536	2
85	1000	262144	65536	2
86	1000	262144	65536	2
87	1000	262144	65536	2
88	1000	262144	65536	2
89	1000	262144	65536	2
90	1000	262144	65536	2
91	1000	262144	65536	2
92	1000	262144	65536	2
93	1000	262144	65536	2
94	1000	262144	65536	2
95	1000	262144	65536	2
96	1000	262144	65536	2
97	1000	262144	65536	2
98	1000	262144	65536	2
99	1000	262144	65536	2
100	1000	262144	65536	2
101	1000	262144	65536	2
102	1000	262144	65536	2
103	1000	262144	65536	2
104	1000	262144	65536	2
105	1000	262144	65536	2
106	1000	262144	65536	2
107	1000	262144	65536	2
108	1000	262144	65536	2
109	1000	262144	65536	2
110	1000	262144	65536	2
111	1000	262144	65536	2
112	1000	262144	65536	2
113	1000	262144	65536	2
114	1000	262144	65536	2
115	1000	262144	65536	2
116	1000	262144	65536	2
117	1000	262144	65536	2
118	1000	262144	65536	2
119	1000	262144	65536	2
120	1000	262144	65536	2
121	1000	262144	65536	2
122	1000	262144	65536	2
123	1000	262144	65536	2
124	1000	262144	65536	2
125	1000	262144	65536	2
126	1000	262144	65536	2
127	1000	262144	65536	2
128	1000	262144	65536	2
129	1000	262144	65536	2

Submit