자력갱생하여 어렵게 창업하다.그래, 자신을 믿어, 할 수 있어.이 문제는 나의 사고방식이 대충 뚜렷하다. 이것은 방향도이다. 먼저 각자의 강연통 블록을 구한 다음에 축소점을 만들어DAG를 형성한 다음에 이 위에서 dp를 뛴다.만약 강연통분량의 값이 모든 점수라면 이 연통 블록 내점의 개수가 바로 답이다.사실 유방향 무환도에 있는 dp는 매우 고전적인 것이니 주의해야 한다.힘내라, 자신을 믿어라.참, 여기에는 중복된 변이 많다고 하는데 축소할 때 DAG이기 때문에 두 개의 강연통분량 사이에 이미 연결이 있는지 병렬로 조사하여 판단한다.
1 #include<cstdio>
2 #include<iostream>
3 #include<stack>
4 #include<vector>
5 #define rep(i,j,k) for(int i = j; i <= k; i++)
6 #define maxn 10005
7 using namespace std;
8
9 vector<int> g1[maxn], b[maxn], g2[maxn];
10
11 int read()
12 {
13 int s = 0, t = 1; char c = getchar();
14 while( !isdigit(c) ){
15 if( c == '-' )t = -1; c = getchar();
16 }
17 while( isdigit(c) ){
18 s = s * 10 + c - '0'; c = getchar();
19 }
20 return s * t;
21 }
22
23 int pre[maxn], low[maxn], cnt = 0, bcnt = 1;
24 int sccno[maxn], num[maxn];
25 stack<int> s;
26
27 void dfs(int now)
28 {
29 s.push(now); pre[now] = low[now] = ++cnt;
30 int sz = g1[now].size();
31 rep(i,0,sz-1){
32 int to = g1[now][i];
33 if( !pre[to] ){
34 dfs(to), low[now] = min(low[now],low[to]);
35 }
36 else if( !sccno[to] ) low[now] = min(low[now],pre[to]);
37
38 }
39 if( pre[now] == low[now] ){
40 for(;;){
41 int x = s.top(); s.pop();
42 b[bcnt].push_back(x);
43 num[bcnt]++;
44 sccno[x] = bcnt;
45 if( x == now ) break;
46 }
47 bcnt++;
48 }
49 }
50
51 int fa[maxn], rank[maxn];
52 int find(int x)
53 {
54 return x == fa[x] ? x : fa[x] = find(fa[x]);
55 }
56 bool bing(int x,int y)
57 {
58 int kx = find(x), ky = find(y);
59 if( kx != ky ){
60 if( rank[kx] > rank[ky] ){
61 fa[ky] = kx; rank[kx] += 1;
62 }
63 else {
64 fa[kx] = ky, rank[ky] += 1;
65 }
66 return 1;
67 }
68 else return 0;
69 }
70
71 void suo()
72 {
73 rep(i,1,bcnt-1) fa[i] = i;
74 rep(i,1,bcnt-1){
75 int s = b[i].size();
76 rep(j,0,s-1){
77 int x = b[i][j];
78 int sz = g1[x].size();
79 rep(k,0,sz-1){
80 int to = g1[x][k];
81 if( sccno[to] != sccno[x] ){
82 if( bing(sccno[to],sccno[x]) )
83 {
84 g2[sccno[x]].push_back(sccno[to]);
85 }
86 }
87 }
88 }
89 }
90 }
91
92 int n, m, f[maxn];
93
94 int road(int now)
95 {
96 if( f[now] ) return f[now];
97 f[now] = 0;
98 int s = g2[now].size();
99 rep(i,0,s-1){
100 int to = g2[now][i];
101 f[now] += road(to);
102 }
103 return f[now] += num[now];
104 }
105
106 int solve()
107 {
108 rep(i,1,bcnt-1){
109 if( !f[i] ) road(i);
110 }
111 int ans = 0;
112 rep(i,1,bcnt-1){
113 if( f[i] == n ) ans += num[i];
114 }
115 return ans;
116 }
117
118 int main()
119 {
120 n = read(), m = read();
121 rep(i,1,m){
122 int x = read(), y = read();
123 g1[y].push_back(x);
124 }
125 rep(i,1,n){
126 if( !pre[i] ) dfs(i);
127 }
128 suo();
129 cout<<solve()<<endl;
130 return 0;
131 }