hdu--3836--tarjan+缩点

缩点很简单的啊... 就是将原来一个连通块变成一个点..

可能你原本是这样的 A->B->C->A 缩点完成后我们就把{A，B,C}用数字1来表示如果还有D->E->D 那我们再讲{D,E}用2表示....

最后的sum就是代表连通块总的个数

然后一般缩点完成后我们现在得到了n个连通块我们要考虑的是最少需要添加几条边来把它串联起来

这样考虑

假如给你2个点 A B 想要让他们联通需要在他们之间建立两条边分别是A->B B->A 你会发现这样 A B的入度出度分别从0变成了1

如果是这样的情况那么现在A的出度为2 入度为0 B和C的出度为0 入度为1 我们只需要B->A C->A建立边就可以了

这样我们就能达到B C的出度增加 A的入度增加

其实是因为在任何一个连通图中每个点的入度和出度都是>=1这样才能达到让别人联向自己自己通向别人

所以我们只需要求出在缩点完成后的图中入度为0 与出度为0的点的个数大小就可以了取大的

******************

如果是做题的话有一点要小心很容易WA在这里..不能直接判断max(in,out)来输出而是首先判断缩点后的图是不是连通图是的话就直接输出0了如果直接输出max(in,out)就是1了.......

  1 #include <iostream>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <stack>
  5 using namespace std;
  6 
  7 int n , cnt , index , sum;
  8 const int size = 20010;
  9 struct data
 10 {
 11     int st;
 12     int end;
 13 }node[size*3];
 14 struct graph
 15 {
 16     int to;
 17     int next;
 18 }edge[size*3];
 19 int head[size];
 20 int father[size];
 21 int No[size];
 22 int scc[size];
 23 int in[size];
 24 int out[size];
 25 bool vis[size];
 26 stack<int>s;
 27 
 28 void init( )
 29 {
 30     memset( head , -1 , int*sizeof(n+10) );
 31     memset( No , 0 , int*sizeof(n+10) );
 32     memset( father , 0 , int*sizeof(n+10) );
 33     memset( vis , false , int*sizeof(n+10) );
 34     memset( scc , 0 , int*sizeof(n+10) );
 35     memset( in , 0 , int*sizeof(n+10) );
 36     memset( out , 0 , int*sizeof(n+10) );
 37 }    
 38 
 39 void add( int st , int end )
 40 {
 41     edge[cnt].to = end;
 42     edge[cnt].next = head[st];
 43     head[st] = cnt ++;
 44 }
 45 
 46 void tarjan( int u )
 47 {
 48     int v , temp;
 49     No[u] = father[u] = index++;
 50     vis[u] = true;
 51     s.push(u);
 52     for( int i = head[u] ; ~i ; i = edge[i].next )
 53     {
 54         v = edge[i].to;
 55         if( !No[v] )
 56         {
 57             tarjan(v);
 58             father[u] = min( father[u] , father[v] );
 59         }
 60         else if( vis[v] )
 61         {
 62             father[u] = min( father[u] , No[v] );
 63         }
 64     }
 65     if( father[u] == No[u] )
 66     {
 67         sum ++;
 68         while(1)
 69         {
 70             temp = s.top();
 71             s.pop();
 72             vis[temp] = false;
 73             scc[temp] = sum;
 74             if( father[temp] == No[temp] )
 75                 break;
 76         }
 77     }
 78 }
 79 
 80 int main()
 81 {
 82     cin.sync_with_stdio(false);
 83     int m , st , end , inMax , outMax;
 84     while( cin >> n >> m )
 85     {
 86         inMax = outMax = cnt = sum = 0;
 87         index = 1;
 88         init();
 89         for( int i = 0 ; i<m ; i++ )
 90         {
 91             cin >> st >> end;
 92             add( st , end );
 93             node[i].st = st;
 94             node[i].end = end;
 95         }
 96         for( int i = 1 ; i<=n ; i++ )
 97         {
 98             if( !No[i] )
 99                 tarjan(i);
100         }
101         for( int i = 0 ; i<m ; i++ )
102         {
103             if( scc[ node[i].st ]!=scc[ node[i].end ] )
104             {
105                 out[ scc[node[i].st] ] ++;
106                 in[ scc[node[i].end] ] ++;
107             }
108         }
109         for( int i = 1 ; i<=sum ; i++ )
110         {
111             if( !in[i] )
112                 inMax ++;
113             if( !out[i] )
114                 outMax ++;
115         }
116         if( sum==1 )
117             cout << "0" << endl;
118         else
119             cout << max( inMax , outMax ) << endl;
120     }
121     return 0;
122 }

View Code

因为这里的数组要开的TM的实在是太多了所以我用了 (n)*sizeof(int)来初始化我测了下节约了15ms....

today:

　　后来我终于知道

　　它并不是我的花

　　我只是恰好途径了它的盛放

just follow your heart