BZOJ 1051 인기 소 강연통

자력갱생하여 어렵게 창업하다.그래, 자신을 믿어, 할 수 있어.이 문제는 나의 사고방식이 대충 뚜렷하다. 이것은 방향도이다. 먼저 각자의 강연통 블록을 구한 다음에 축소점을 만들어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 }